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 \chi-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 K_k 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 \mathcal{C}(G) be the set of cycle lengths in a graph G and let \mathcal{C}_\text{odd}(G) be the set of odd numbers in \mathcal{C}(G). We prove that, if G has chromatic number k, then \sum_{\ell\in  \mathcal{C}_\text{odd}(G)}1/\ell\geq (1/2-o_k(1))\log k. 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 d) 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 k, there is some d so that every graph with average degree at least d has a subdivision of the complete graph K_k in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.

This entry was posted in Combinatorics and tagged , , , , . Bookmark the permalink.

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

  1. domotorp says:

    Maybe I’ve misunderstood something, but doesn’t your stronger conjecture fail for the complete graph?

  2. Pingback: Graphs, chromatic numbers and a positive answer – The nth Root

  3. ryeguy10 says:

    You wrote Montgomry instead of Montgomery in a couple of places.

    GK:Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s