In 1981, ErdH{o}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_{ellin mathcal{C}_text{odd}(G)}1/ellgeq (1/2-o_k(1))log k$. This solves ErdH{o}s and Hajnals odd cycle problem, and, furthermore, this bound is asymptotically optimal. In 1984, ErdH{o}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.
Download