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 https://www.dpmms.cam.ac.uk/~dc340/Extremal-course.html

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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: