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

26 January 2021
Richard Montgomery

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.


I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant $C$ such that every graph with average degree at least $C$ contains a cycle whose length is a power of 2.

  • Combinatorial Theory Seminar