Posted by: holdenlee | December 5, 2013

Szemeredi Regularity and Roth’s Theorem

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.


  1. Reblogged this on John Pappas's blog.

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: