Combinatorics Seminar

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

ABSTRACT:

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.

Event Type

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

MIT Community

Events By School

School of Science

Website

http://math.mit.edu/seminars/combin/

Department
Department of Mathematics
Add to my calendar

Recent Activity