UBC Math Department Colloquium: Jacob Fox

Szemerédi's regularity lemma and its variants are some of the most powerful tools in combinatorics. For example, Szemerédi used an early version in the proof of his celebrated theorem on long arithmetic progressions in dense sets of integers. It has also played a central role in extremal combinatorics, additive combinatorics, and in algorithmic problems including property testing. The regularity lemma roughly says that the vertex set of every graph can be partitioned into a bounded number of parts such that for most of the pairs of parts, the bipartite graph between the pair is quasirandom. A substantial drawback in using the regularity lemma is that it typically gives enormous, tower-type bounds in its various applications. A major program over the last few decades has been to find alternative proofs of the many applications of the regularity lemma with much better quantitative bounds. We will discuss the current status of the program, which includes some big successes, as well as the first examples of applications in which the tower-type bounds which come from applying a regularity lemma is necessary.