Long cycles in graphs
Vienna Combinatorics Seminar
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 Erds and Gallai, which states that the same conclusion holds if we only assume that the average degree is d.
Although the Erds–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 Erds–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.