Graduate Combinatorics Seminar
Lujia Wang
Proof of Szemerédi's Regularity Lemma (Part II)
Abstract: Szemerédi developed his graph theoretical tool (the regularity lemma) in 1970s for proving a result on the Ramsey preperties of artithmetic progressions now known as Szemerédi's theorem. The lemma roughly states that every graph can be partitioned into bounded number of equal parts (with a small exceptional set) such that the edges between most of the pairs behave like random bipartite graphs. This turned out to be of much importance in extremal problems in graph theory. We will show a standard proof of this lemma and probably some applications.
Wednesday October 8, 2014 at 4:00 PM in SEO 512