# How to “explain” Szemerédi's Regularity Lemma so that classmates may understand its value?

I am a student, preparing myself for a talk in which I want to present and prove Szemerédi's Regularity Lemma. I understand the proof and I am able to reproduce it - that is no problem. But I am afraid, that the proof is very "technical" and my classmates won't gain very much insight from it, if they see me jumble up partitions of sets and greek letters. (For the sake of completeness: I am using the approach described in the englisch version of the book Graph Theory from R. Diestel)

So to breathe a little life in my talk and to make the lemma more attractiv I want to explain its usefullness and its power, so they get a mental picture which will hopefully hinder them falling asleep. :-) I did some research in the web, but the descriptions I found in the articles and papers are most often the same: Szemerédi's Lemma asserts that, very roughly speaking, any dense graph can be decomposed into a bounded number of pseudorandom bipartite graphs. The book I use, uses the Lemma to prove the proposition of Erdős and Stone from 1946. But I don't have the time to explain that too.

So my question is: How would you make classmates who have no experience in Extremal Graph Theory and know only the basics in Graph Theory understand that the lemma has a big value without diving too deep in stuff that would overcharge them?

I am thankful about any sharing of experience and any advice. Hopefully I am not asking too much. :-)

-
You could mention that Szemerédi's original motivation for the Regularity Lemma was proving what is now known as Szemerédi's Theorem: Every subset of integers of positive upper density has an arbitrarily long arithmetic progression. This statement might not be what you're looking for exactly, but it at least provides some motivation of what you'll do next. –  JavaMan Oct 26 '11 at 23:03
Ernie Croot has a proof too (cs.umd.edu/~gasarch/vdw/notesregularity.pdf) and he first explains that the probabilistic method fails, showing the strength of the regularity method. This might be another option. He is also a great expositor so his proof might be worth looking at (if you have not already done so). –  JavaMan Oct 26 '11 at 23:06
@JavaMan I gained much insight from Mr. Croots way of prooving the Regularity Lemma. Thank you very much for providing the link. –  Aufwind Oct 29 '11 at 16:50
@JavaMan link is down for me –  dREaM Aug 18 '13 at 3:42

I think proofs using the Triangle Removal Lemma (derived from the Regularity Lemma) gives a very nice example of the power of the Regularity Lemma. For example you can state Roth's Theorem (1952 IIRC) regarding 3-length arithmetic progressions. There are several other good examples, but the TRL is a very useful and and always appears like a kind of "magic" (you build a graph of $\epsilon n^2$ disjoint triangle, and suddenly you got many more giving you some crazy results.