Friday, December 01, 2017 at 4:15pm to 5:15pm
Microsoft Research/MSR 1st Floor Conference Ctr/One Memorial Drive, Cambridge, MA
SPEAKER: Guy Moshkovitz (Harvard University)
TITLE: Tight bounds for Regular Lemmas
Regularity Lemmas are some of the most powerful tools in Graph Theory and Computer Science (and Number theory and Discrete Geometry...). Due to their many applications, determining the best possible bounds for them was and remains a question of considerable interest. In this talk I will discuss several such lemmas, both old and new, and describe a series of works culminating in a recent proof (with A. Shapira) of an Ackermann-type lower bound for the hypergraph regularity lemma, thus confirming a prediction of Tao. Prior to this work, the only result of this kind was Gowers' famous lower bound for graph regularity.
Based on joint works with Kaave Hosseini, Shachar Lovett and Asaf Shapira.