Christopher Lambie-Hanson: Chromatic numbers of finite subgraphs

Talk held by Christopher Lambie-Hanson (Virginia Commonwealth University, Richmond, USA) at the KGRC seminar on 2019-03-14.

Abstract: By the De Bruijn-Erdős Compactness Theorem, if a graph $G$ has infinite chromatic number, then it has finite subgraphs of arbitrarily large finite chromatic number. We can therefore define an increasing function $f_G:\omega\to \omega$ by letting $f_G(n)$ be the least number of vertices in a subgraph of  $G$ with chromatic number $n$. We will show in ZFC that, for every function $f:\omega\to \omega$ there is a graph $G$ with chromatic number $\aleph_1$ such that $f_G$ grows faster than $f$. This answers a question of Erdős, Hajnal, and Szemeredi. Time permitting, we will discuss connections between our proof and various diamond and club-guessing principles.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.