Szemerèdi Regularity Lemma

Regarding triangle removal lemma, I recommend for further reading:

1) The paper “Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs” by W. T. Gowers (it is interesting to see how this lemma can be generalized to hypergraphs) and

2) these excellent online notes by David Conlon

Lemma Meringue

Welcome to the first in our series about Great Lemmas of Mathematics. We’ll start with one of the greats from combinatorics, perhaps the most useful tool in combinatorics and graph theory: the Szemerèdi Regularity Lemma (SRL). This was first proved by Szemerèdi (unsurprisingly) in his 1975 paper “On sets of integers containing no $latex k$ elements in arithmetic progression” as part of his proof of what is now known as Szemerèdi’s theorem – a cornerstone of additive combinatorics and one which I’m sure we’ll come back to in a future post.

This lemma turned out to be very powerful and versatile, and new and exciting results which use SRL have appeared at regular intervals ever since. Gowers has compared the SRL to playing the same role in combinatorics as the classification of finite simple groups has in finite group theory, providing a rough classification of all graphs, and offering a…

View original post 915 more words


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: