Laszlo Lovasz: The height of the tower in the Regularity Lemma

Szemerédi's regularity lemma has become one of the most commonly used tools in graph theory. It roughly states that any graph can be divided into a bounded number of parts (of almost equal size), such that the graph between most pairs is "randomlike". One method of formulating this precisely is adding up, for each pair of parts, how far they are from being "random" (or quasirandom), and having a bound on this sum, that depends on a parameter epsilon.

The standard proof of the lemma gives a bound on the number of parts that is a tower of twos, the height of which is a constant times the inverse of epsilon squared. A breakthrough result of Gowers showed that this does have to be a tower of height polynomial in the inverse of epsilon. In the talk, we give a construction that gives a lower bound that is also a tower of height a constant times the inverse of epsilon squared, matching the upper bound. We will give an outline of the proof.

Joint work with Jacob Fox.