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

Abstract

In an $n$-vertex graph, it is simple to see that $n$ edges imply the graph has a cycle. However, this cycle can be any length from $3$ to $n$. If we have more edges, do we get cycles of many different lengths? Can we find a cycle with some control over its length? In this talk, based on joint work with Hong Liu, I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on even and odd cycles. in 1984, Erdős asked whether there is a constant $C$ such that every $n$-vertex graph with at least $Cn$ edges contains a cycle whose length is a power of $2$. In 1981, Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases.

Speaker Intro

Richard Montgomery is an Associate Professor at the Mathematics Institute at the University of Warwick, whose primary research interests are in extremal and probabilistic combinatorics. He obtained his PhD in 2015 from the University of Cambridge under the supervision of Andrew Thomason. Prior to joining Warwick in 2022, he was a faculty member of the University of Birmingham from 2018, and held a Junior Research Fellowship at Trinity College, Cambridge, from 2015-2019. He received a Philip Leverhulme Prize in 2020 and the European Prize in Combinatorics with Alexey Pokrovskiy in 2019, and his research is currently supported by an ERC Starting Grant.