Algebra Seminar talk
2026-11-06
Peter Holy
Compactness for graph colouring with infinitely many colours
Abstract:
I will talk about a recent joint paper with Roman Feller, that investigates compactness properties with respect to graph colouring and connects these with axioms of large infinities. No knowledge of set theory is required to follow this talk. It will be helpful to have a basic knowledge about cardinals, but I will provide a brief introduction that should be sufficient.
A classical theorem about infinite graphs (De Bruijn-Erdos (1951), Läuchli (1971)) is that over the basic system of Zermelo Fraenkel set theory (ZF), the statement that for every graph G, if G is such that every finite subgraph of G can be 3-coloured (meaning that we assign one of the colours 0,1,2 to each of its nodes, so that any two adjacent nodes obtain different colours), then also G itself can be 3-coloured, is equivalent to a weak form of the axiom of choice that is the ultrafilter lemma (this states that any filter on a set S can be extended to an ultrafilter on that set). We establish generalizations of this result for graph colourings with infinitely many colours, thus obtaining new characterizations of prominent notions of large infinities, like strongly compact and weakly compact cardinals. (All our results are over the basic system ZFC, that is ZF with the axiom of choice.)