Szemeredi Regularity and Roth’s Theorem

Mental Wilderness

I’m giving a talk today at the Part III seminars (at the University of Cambridge). Notes are available here:

Abstract: The Szemeredi Regularity Lemma is the graph-theoretic analogue of the dichotomy between order and randomness. It states that any large enough graph can be described using a structured component of bounded complexity with small error, the error being the pseudorandom component of the graph. I’ll sketch a proof using the energy increment argument, and then apply it to prove Roth’s Theorem: that any set of positive density in the naturals has a 3-term arithmetic progression.

View original post


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: