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. :-)


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.

Another option, is to prove the Erdős-Stone theorem, which is much simpler to do using the Regularity Lemma.