Jacob Fox: The graph regularity method
Time: Mon 2014-03-31 12.10 - 13.00
Location: Room 3721, Lindstedtsvägen 25, 7th floor, Department of mathematics, KTH
Practicalities
Lunch is served at 12:00 noon (register at this doodle by Sunday March 30 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
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 with many further applications. In this talk, I will survey recent progress in understanding the quantitative aspects of these lemmas and their applications.