A solution to Erdős and Hajnal's odd cycle problem

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 \ge (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.

42 pages, 3 figures. Version accepted for publication

Cited by in corpus (2)

• Well-mixing vertices and almost expanders
• Balanced subdivisions of a large clique in graphs with high average degree