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.

Advertisements

## Leave a Reply