To cheer you up 14: Hong Liu and Richard Montgomery solved the Erdős and Hajnal’s odd cycle problem

The news: In 1981, Paul Erdős and András Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Hong Liu and Richard Montgomery have just proved that the answer is positive!  They also proved a variety of other old standing conjectures. This is remarkable. Congratulations!

Before going on let me pose an even stronger conjecture

Conjecture: The sum of the reciprocals of the odd induced cycle lengths in a triangle-free graph with no triangles and infinite chromatic number is necessarily infinite.

The same conclusion should apply to graphs with bounded clique numbers; it is related to the general area of -boundedness, see this post and this recent survey by Alex Scott and Paul Seymour.

Returning to Liu and Montgomery’s breakthrough, let me mention two other conjectures that Hong and Richard proved in the same paper:

A) (Conjecture by Erdős from 1984) There is a constant d such that any graph with average degree d has a cycle whose length is a power of 2.

B) (Conjecture by Carsten Thomassen from 1984) for every k, there is some d so that every graph with average degree at least d has a subdivision of the complete graph in which each edge is subdivided the same number of times.

I am thankful to Benny Sudakov for telling me about the new result.

A key ingredient of the proof is the study of expanders that you can always find in graphs. Komlós and Szemerédi showed in 1996 that every graph G contains an expander with comparable average degree to G and since their work, with greater and greater sophistication, finding expanders in general graphs has become an important tool for a large number of extremal problems.

Hong Liu, Richard Montgomery: A solution to Erdős and Hajnal’s odd cycle problem (click for the arXive.)

Abstract:

In 1981, Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Let be the set of cycle lengths in a graph and let be the set of odd numbers in . We prove that, if has chromatic number , then This solves Erdős and Hajnal’s odd cycle problem, and, furthermore, this bound is asymptotically optimal.
In 1984, Erdős asked whether there is some d such that each graph with chromatic number at least d (or perhaps even only average degree at least ) has a cycle whose length is a power of 2. We show that an average degree condition is sufficient for this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2.
Finally, we use our methods to show that, for every , there is some so that every graph with average degree at least d has a subdivision of the complete graph in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.