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: 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

Responses

  1. Reblogged this on John Pappas's blog.


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

Categories

%d bloggers like this: