Vienna Combinatorics Seminar

Long cycles in graphs

A simple exercise appearing in many graph theory courses is that if a graph has minimum degree d, then it contains a cycle of length at least d+1. A substantially more challenging generalization of this is a celebrated theorem of Erdős and Gallai, which states that the same conclusion holds if we only assume that the average degree is d. 

Although the Erdős–Gallai theorem has a relatively short proof, I personally find it somewhat mysterious and unenlightening. In this talk, I will discuss a new proof of the Erdős–Gallai theorem, which has the disadvantages of being a lot more complicated and of proving a somewhat weaker statement. However, its advantages are (a) that it sheds more light on why such a statement should be true, and (b) that it can also be used to prove some interesting and surprising generalizations. Along the way, I will discuss a remarkable recent result of Pokrovskiy, which reveals a great deal about the structure of sparse graphs. 

Based on joint work with Micha Christoph and Alp Müyesser.