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: https://dl.dropboxusercontent.com/u/27883775/math%20notes/cnt.pdf

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

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: