A prominent line of inquiry in the study of infinite graphs concerns the extent to which global properties of an infinite graph are determined by the structure of the set of its finite subgraphs. In this talk, we consider a question in this direction concerning chromatic numbers of graphs. By a classic result of De Bruijn and Erdős, if a graph G has infinite chromatic number, then it has finite subgraphs of every finite chromatic number. We prove, however, that even for a graph with uncountable chromatic number, the chromatic numbers of its finite subgraphs can grow arbitrarily slowly. In particular, we prove that, for every function f:ℕ → ℕ, there is a graph G of uncountable chromatic number such that, for every natural number k ≥ 3 and every subgraph H of G with at most f(k) vertices, the chromatic number of H is at most k. This answers a question of Erdős, Hajnal, and Szemerédi from 1982.

Here is the video of Chris' talk.