ragde@utcsri.UUCP (04/20/87)
Interest has been expressed in holding a series of informal meetings
to study Ramsey theory. The basic idea is that we would decide on a list
of topics and take turns presenting the proofs to each other. I think
it would be better if only people who are actively involved come to
these meetings - i.e., attendance commits you to making a presentation.
We would probably use the Graham, Rothschild & Spencer book, plus
additional papers as needed. Below is a list of topics from that book
that are within the scope of something like this. I'd like people to
let me know if they are interested, and what topics specifically they
would like to see covered. This wouldn't start until late summer or
maybe even early fall. If there is a LOT of interest, it could be
made a course, but I hesitate to do this...--PR
Full Proof of Ramsey's Theorem
The method of Induced Colouring, which is a paradigm for many subsequent
proofs.
Compactness
How infinite versions of Ramsey theorems imply finite versions.
Van Der Waerden's Theorem
If N is finitely coloured then there exists a colour class containing
arbitrarily long arithmetic progressions. Note that it is not possible
to find infinite monochromatic arithmetic progressions.
Hales-Jewett Theorem
If all vectors of length n with components from {1..t} are coloured
with r colours, then for n sufficiently large, there exists a
monochromatic line - that is, a set of vectors x_1,...,x_n such that
the ith component of x_j is either constant as j varies, or equals j.
This implies other useful theorems - in particular, VDW's Theorem.
Upper and Lower Bounds for Ramsey Numbers
Probabilistic methods and explicit constructions; we should also do
the Lovasz local lemma, giving conditions under which all of n events
occur with nonzero probability (as is needed for existence proofs using
the probabilistic method) even if some events are dependent.
Induced Ramsey Theorems
For any graph G, there exists a graph H such that if the vertices
[edges] of G are coloured with r colours, then there exists an
induced subgraph of H which is a monochrome G.
Restricted Ramsey Theorems
We know that any 2-coloured K_6 contains a monochrome K_3. Does
there exist a graph G such that any 2-colouring induces a monochrome
triangle, and the clique number of G is 3? What about any number of
colours, and any size monochrome clique?
Canonical Ramsey Theorems
No restrictions on the number of colours; what sort of results can
we prove? (These have proved useful in lower bounds for parallel
machines - an unrestricted colouring is just a function from the
input vectors to some range, and these theorems prove that we
can restrict input vectors and give such functions useful properties.)
Euclidean Ramsey Theorems
Suppose we colour every point of R^n with one of two colours. Does
there exist a monochrome equilateral triangle of side 1? No if n=2,
yes if n=4. Generalize...
Graph Ramsey Theory
We define R(G,H) to be the smallest number n of vertices such that
if we 2-colour a K_n, either there exists a G of colour 1 or an
H of colour 2. An example of a theorem is:
R(tree with m vertices, K_n) = (m-1)(n-1)+1
Another is: in any 2-colouring of K_5n there exist n disjoint triangles
of the same colour; 5n is the best possible result. (n>1).
Independence Results
Some variations of Ramsey's Theorem can be shown unprovable in Peano
arithmetic. Godel's Theorem shows that unprovable statements exist, but
this was the first "natural" one. It can be shown both by
model-theoretic methods and by lower-bounding the growth rate of
associated functions.
Infinite Ramsey Theory
If all 2-subsets of the natural numbers are 2-coloured, there exists
a countably infinite monochrome subset. This is not true for the
real numbers if we want an uncountable monochrome subset. What can
we say about the reals, and higher cardinals and ordinals? Any cardinal
bigger than omega that has the property above must be "inaccessible" -
among other things, not reachable by power sets or limits from the
usual type of cardinals. Weirdnesses out past infinity...
Other topics will be considered as we come across them in journal searches
or hear of more recent proofs. --PR