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 nontrivial. 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.
