Advances on regularity methods and its applications

To be held at ESB 2012 and on Zoom: https://ubc.zoom.us/j/68285564037?pwd=R2ZpLy9uc2pUYldHT3laK3orakg0dz09
Meeting ID: 682 8556 4037
Passcode: 636252

Reception and refreshments at 14:30 in the PIMS lounge, ESB 4th floor.

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.