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

Abstract: 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. In 1966, 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. Later, 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.

This is joint work with Hong Liu.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).