The contents and opinions expressed on this web page do not necessarily reflect the views of  nor are they endorsed by the university system of georgia
Last modified 17 June 2005
Ramsey Theory  
                                                  
REU Summer 2005

Akos Magyar & Neil Lyall

Ramsey theory is a beautiful area, as its principal results are both natural, easy to formulate and non-trivial. Roughly speaking, it deals with finding regular structures in large but otherwise arbitrary sets. The theorem of Ramsey itself (often called the "party theorem") can be formulated as follows: let k be a natural number. Then for any sufficiently large dinner party you can find a group of k people, who are either (a) mutual acquaintances, or (b) complete strangers to one another. The smallest such dinner party is only known however for k=3 and k=4.

There are three basic approaches to such problems: via combinatorics, ergodic theory and elementary Fourier analysis. A famous example is Szemerédi's theorem, stating that if a set contains a "positive proportion" of the natural numbers, then it must contain arbitrary long arithmetic progressions. This was first proved via combinatorics, and elements of the proof have become influential on the development of the subject. Later a different proof was given using ideas from dynamics going back to Poincare, and more recently by a spectacular application of Fourier analysis (which won the Fields medal in '98).

As deep as such results may be, nevertheless they require little formal knowledge, and our aim will be to understand the basic ideas behind them through exercises, problems and studying articles, with an eye toward some related open problems.
The Group
Joseph
The Group II


Text: Ramsey Theory on the Integers  by Landman and Robertson

Supplements:  
The expository note on Arithmetic Ramsey Theory by Terry Tao covers much of the same material.
A great deal of other related material can also be found on the web page of  Terry Tao.    
                

Core Material:

  1. Ramsey's Theorem 
    • Chapter 1 of the text
  2. Two contrasting proofs of Fermat's Last Theorem mod p (Schur's Theorem)
  3. Van der Waerden and Gallai's Theorem
  4. Roth's Theorem I
    • A short exposition of Behrend's example which gives a lower bound on the size of the largest subset of [1,N] that does not contain any arithmetic progressions of length three
  5. Roth's Theorem II

Supplementary Material:

Problems/Projects:
  1. Topological proof of van der Waerden's theorem (and Gallai's theorem)
    • Josef is preparing notes on this based on the presentation in Elemental Methods in Ergodic Ramsey Theory by R. McCutcheon. there is also a presentation in the classic book on Ramsey theory by Graham, Rothschild, and Spencer
    • * Using these methods one can also prove the polynomial analogues of these results
  2. Problems relating to Gallai's Theorem
    • Axes parallel triangles: Color the points of an N by N square with r colors. Use the proof of Gallai's theorem to find a number N(r) such that if N is at least N(r), then in any r-coloring there is a monochromatic right isosceles triangle parallel to the coordinate axes
    • (Skewed) triangles: Modify the argument to find a smaller number M(r), such that that if N is at least M(r), then in any r-coloring there is a monochromatic right isosceles triangle which is necessarily not parallel to the coordinate axes
    • Lower bounds: Also try to think of possible r-colorings where there are no monochromatic triangles of the above type, therefore obtaining lower bounds for N(r) or M(r)
    • Equilateral triangles: An essentially equivalent version of the above problem is as follows. Consider an equilateral triangle of side length N. Divide it into N*N equilateral triangles of size 1, by dividing each side into N equal parts. Color the points of the grid you obtained this way with r colors. Find bounds N'(r) and M'(r) as to guarantee a monochromatic equlateral triangle parallel to the original triangle, or just any monchromatic equilateral triangle
    • * One could think about the polynomial analogues of Van der Waerden and Gallai, these are discussed in Tao's notes on Arithmetic Ramsey Theory
    • Brandon has prepared an alternative set of notes on Gallai's theorem
  3. Rado's theorem
    • A guide to the proof of Rado's Theorem for a single equation
    • * The expository note on Arithmetic Ramsey Theory by Terry Tao covers the extension of Rado's theorem to a system of equations, see also the book of Graham, Rothschild, and Spencer
    • One can also formulate a density version of Rado's theorem for translation invariant equations, see the Fourier analysis projects below
  4. The Regularity Lemma and another combinatorial proof of Roth's theorem
  5. Adaptations of the Fourier analytic proof of Roth's theorem
    • Adapt the Fourier analytic proof of Roth's theorem to find an upper bound on the size of the largest subset of [1,N]^2 that does not contain any right angled isosceles triangle of any orientation. What are the best upper (and lower) bounds you can obtain for the size of this set?  Try using a weaker notion of randomness to improve on the upper bounds, can you construct any sort of example that would give a lower bound?
    • A density version of Rado's theorem for translation invariant equations was proposed in Additional exercises 3
    • Here is an exposition by Ben Green of Szemeredi's argument to improve Roth's bound. Can you apply this argument to improve on the bounds in either Roth's theorem for triangles or the density version of Rado's theorem for translation invariant equations?

(Much?) Longer term projects: