Szemerédi's Regularity Lemma, Variants, and Applications <br><em> Introduced by: Van Vu</em>

Friday, November 30, 2012 - 2:00pm - 3:00pm
Keller 3-180
Jacob Fox (Massachusetts Institute of Technology)
Szemerédi's regularity lemma is one of the most powerful tools
in graph theory, with many applications in combinatorics, number theory,
discrete geometry, and theoretical computer science. Roughly speaking, it
says that every large graph can be partitioned into a small number of parts
such that the bipartite subgraph between almost all pairs of parts is
random-like. Several variants of the regularity lemma have since been
established yielding many further applications. In this talk, I will survey
this area, including recent progress on quantitative estimates in the
various regularity lemmas, and alternative methods yielding new proofs of
applications with improved quantitative estimates.
MSC Code: