Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 ( 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 – Carry on Smiling 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.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.