Description
As one of the first results of the probabilistic method Pál Erdős proved in 1959 that high girth high chromatic number graphs exist. Shortly after, they asked with András Hajnal if these graphs are ubiquitous, namely, whether for every g and k there exist a K=K(g,k) such that every K-chromatic graph has a k-chromatic subgraph of girth at least g. Vojtěch Rödl proved this "Erdős-Hajnal conjecture" for g=4 (i.e. triangle-free subgraphs) in 1977 but the conjecture is open for all higher girth.
In this talk we consider Burling graphs introduced by James Burling in 1965. They form a very curious family of graphs with unbounded chromatic number and they do satisfy the statement of the conjecture: they have high girth high chromatic number subgraphs, but those must be huge. Using this, we show that K(g,k) (if exists) must grow at least Ackermann-type fast in log g and k.
This is joint research with Seth Pettie and Bartosz Walczak. I gave a talk on this back in May 2025. Back then we could only handle the girth 5 case and proved tower-type lower bound for K(5,k). The
techniques are somewhat different too.