\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Ramsey theory and related topics.}
\end{center}

\bigskip

\noindent 1.  Graph Ramsey theorems.

\medskip

Ramsey-type theorems say that if you have $r$ colors, and you
color all the pieces of some large enough thing, then no matter how
you do it that thing will have
certain substructures in which all the pieces have the same color.
That is, it will have ``monochromatic'' substructures.  We're being
vague about the ``thing'' and the ``substructure'', but that's because
there are many possibilities, and many different Ramsey-type theorems.

The simplest Ramsey theorem allows you to 2-color the edges of a
complete graph $K_{n}$.  The complete graph $K_{n}$ means the graph
with $n$ vertices in
which every pair of vertices is connected by an edge (so it has
${n\choose 2 }$ edges).  It says if $n$ is big enough, you can always
find a monochromatic complete subgraph  $K_{k}$ of specified size $k$,
no matter how the original 2-coloring is done.

\medskip

\noindent {\it Graph Ramsey theorem:}  Let $k$ be given.  Then if $n$
is large enough, for every 2-coloring of the edges of $K_{n}$ there
will be some
$k$ vertices such that the $K_{k}$ consisting of all edges connecting
these vertices is monochromatic.

\medskip

For example, in the Brualdi handout 
it is shown that in every 2-coloring of the
edges of $K_{6}$ there is a monochromatic $K_{3}$.  Informally, one
could say equivalently that in every group of six people there are
either 3 mutual acquaintances or 3 mutual strangers (assuming that any
2 people are either acquaintances or strangers, and 
that it can't happen that that one knows
the other but the other does not know the first).  This says that for
$k=3$, $n=6$ is big enough for the graph Ramsey theorem to hold.

It turns out that the graph Ramsey theorem is easier to prove by
proving something stronger:

\medskip

\noindent {\it Asymmetric graph Ramsey theorem:}  Let $k$ and $l$ be
given.  Then if $n$ is large enough, for every coloring of the edges
$K_{n}$ using two colors, red and blue, there will either be $k$
vertices determining a red $K_{k}$ or $l$ vertices determining a blue
$K_{l}$ (or both).

\medskip

Obviously the symmetric graph Ramsey theorem is the special case of the
asymmetric one in which $k = l$.

We will prove the asymmetric
graph Ramsey theorem by joint induction on $k$ and $l$.
This means that we will prove the theorem for the given $k$ and $l$ by
assuming it holds for the smaller values $k-1$ and $l$, and also $k$
and $l-1$.  When $k$ or $l$ is 2 (the smallest value that makes sense),
the theorem is obviously true (if $k = 2$, take $n = l$; we either
have one red edge---a $K_{k}$---or all blue edges---a $K_{l}$).  These
are the base cases for our induction.

The logical justification for joint induction as a method of proof is
the same as that for ordinary induction:  Suppose the theorem fails
for some value of $k,l$.  Among all such values there would be one for
which $k$ is smallest and among these one for which $l$ is smallest.
Since the theorem holds in the base cases, the bad values would have
$k,l\geq 3$.  Then the values $k-1,l$ and $k,l-1$ are meaningful cases
and since they have smaller $k,l$ values than the smallest bad values,
the theorem holds in these cases.  But the inductive proof then shows
the theorem holds in the case $k,l$ contrary to our assumption that
these were bad values.

Let us now get down to the business of the proof.  From the case of
the theorem for $k-1$ and $l$ find $p$ sufficiently large that
every 2-coloring of $K_{p}$ has a red $K_{k-1}$ or a blue $K_{l}$.
From the case for $k$ and $l-1$ find $q$ sufficiently large that every
2-coloring of $K_{q}$ has a red $K_{k}$ or a blue $K_{l-1}$.

  Let $n = p+q$.  In $K_{n}$ pick out one vertex $v$.  Let any
2-coloring of $K_{n}$ be given.  There are $n-1 = p+q-1$ edges leading
out from $v$.  By the pigeonhole principle, we can find among them at
least $p$ red edges or $q$ blue edges.  Suppose we find $p$ red edges
from $v$.  Let $X$ be the set of $p$ vertices at the other ends of
these $p$ edges.  Consider the $K_{p}$ on the vertex set $X$.  Either
it contains a red $K_{k-1}$ or a blue $K_{l}$.  If it contains a blue
$K_{l}$ we are done.  If it contains a red $K_{k-1}$, then the $k-1$
vertices of this, together with $v$, give a red $K_{k}$ and again we
are done.  In the alternative case, we find $q$ blue edges from $v$
and the same argument works, with $q$ replacing $p$ and the roles of
$k,l$ and red, blue exchanged.  This completes the proof.

\medskip

The preceding proof contains in it an implicit recurrence to find a
suitable value of $n$, given $k$ and $l$, for the theorem to
work.  Namely, if we set $N(2,j) = N(j,2) = j$, and $N(k,l) =
N(k-1,l)+N(k,l-1)$, then the preceding theorem applies with
$n=N(k,l)$.  This is really just the Pascal relation for
binomial coefficients and its solution is $N(k,l) = {k+l-2\choose k-1}$.

It is vital to understand that the proof only shows that
$n ={k+l-2\choose k-1 }$ works, and {\it not} that this is the
smallest value which works.  In particular, for $k=3,l=4$ the proof
shows that every 2-coloring of $K_{10}$ has a red $K_{3}$ or a blue
$K_{4}$.  In fact, however, this is true of $K_{9}$, and $9$ is the
smallest $n$ which works in this case.

Finding the exact smallest value of $n$ which works for given $k$ and
$l$, known as the ``graph Ramsey number'' $R(k,l)$, is a
very difficult problem which has only been solved for small values of
$k$ and $l$.  Here are most of the known exact values: $R(3,3) = 6$,
$R(4,3) = 9$, $R(5,3) = 14$, $R(4,4) = 18$.  $R(6,3)$ and $R(7,3)$ are
also known but I forgot what they are.

Let us prove that $R(4,4) = 18$.  First you must accept that $R(4,3) =
9$ (exercise, not entirely easy without hints).  If you do accept
that, then the proof shows that $n = R(4,3)+R(3,4) = 9+9=18$ is large
enough for the case $k=l=4$.  In other words, $R(4,4)\leq 18$.  To
prove $R(4,4)>17$, we must actually exhibit a 2-coloring of $K_{17}$
containing no monochromatic $K_{4}$.

Here is how to do it.  Number the vertices 0 through 16 and arrange
them in a circle.  Color an edge red if the distance between its ends
along the circle is either 1, 2, 4, or 8, and blue otherwise.

First of all, this coloring has a symmetry between the red and blue
edges.  To see this, suppose you replace each the number $j$ of each
vertex by $3j$, reduced mod 17.  That is, you multiply by three and
then subtract 17 or $34=2\cdot 17$ to get back into the range $0$ to
$16$.  So $0,1,2,3,4,5,6,7,\ldots$ are replaced by
$0,3,6,9,12,15,1,4,\ldots$.  In the original numbering, an edge was
red if the difference between its endpoints was one of $\pm 1,\pm
2,\pm 4\pm 8$, mod 17.  In the new numbering, red edges are those with
differences which are these times 3, namely $\pm 3,\pm 6,\pm 5,\pm 7$,
mod 17 (because $3\cdot 4$ reduces to $-5$ and $3\cdot 8$ to 7).  These
are exactly the differences which were blue edges in the original
numbering.  In other words, by renumbering the vertices we can
switch the red edges with the blue ones in this coloring.
Consequently, there is a red $K_{4}$ if and only if there is a blue
one.

Now we only need to show there is no red $K_{4}$, which is to say,
there are no four numbers whose distances around the circle all belong
to the set $\{1,2,4,8 \}$.  Suppose there were four such numbers.  By
symmetry we can assume one of them is $0$.  The others must then be three
from the set $\{1,2,4,8,9,13,15,16 \}$.  Including $1$ rules out $4$,
$8$, $13$, and $15$.  Including $2$ rules out $8$, $9$, $13$, and
$16$.  In particular, you can't have both $1$ and $2$ since together
they rule out everything else.  But $\{1,9,16 \}$ is no good since $9$
and $16$ are incompatible.  This rules out $1$ entirely.  By symmetry,
$16$ is also ruled out.  That leaves only $\{2,4,8,9,13,15 \}$.  Since
$2$ is compatible only with $4$ and $15$, which are incompatible with
each other, $2$ is ruled out.  By symmetry, $15$ is ruled out.  That
leaves only $\{4,8,9,13 \}$.  Since $4$ is incompatible with $9$ and
$8$ is incompatible with $13$, no three of these are compatible and
everything is ruled out.  So $R(4,4) = 18$.

\bigskip

\noindent 2.  Ramsey's theorem.

\medskip

In the graph Ramsey theorem, coloring $K_{n}$ amounts to assigning a
color to each 2-element
subset of the $n$ vertices, since these are the edges.  Then we look
for a $k$-element subset all of whose 2-element subsets have the first
color, or an $l$-element subset all of whose 2-element subsets have
the other color.

The generalized version of this is Ramsey's theorem, in which we can
have more than 2 colors and we can assign the colors to $t$-element
subsets, where $t$ is arbitrary.  Let's state the theorem.

\medskip

\noindent {\it Ramsey's theorem:} Let positive integers $t$ and
$q_{1},\ldots,q_{r}$ be given.  Then if $n$ is chosen large enough,
for every $r$-coloring of all the $t$-subsets of an $n$-element set
$S$ there is a $q_{i}$-element subset whose $t$-subsets all have color
$i$, for some color $i$.

\medskip

When $t=2$, $r=2$, and $q_{1},q_{2}$ are $k$ and $l$, this reduces to
the asymmetric graph Ramsey theorem.  For general $t$ and $r$, it is a
much stronger statement.

The notation $R(q_{1},q_{2},\ldots,q_{r};t)$ is used for the smallest
value of $n$ that works in Ramsey's theorem for the given parameter
values.  It is called the {\it Ramsey number} for these values.
Our graph Ramsey number $R(k,l)$ is $R(k,l;2)$ in this context.
Brualdi uses the letter $N$ instead of $R$.

We will now prove the theorem.  As before, the proof will
give an implicit recurrence for a suitable value of $n$, but it is
important that you understand that the $n$ computed this way will
usually be bigger that the minimum value
$R(q_{1},q_{2},\ldots,q_{r};t)$.  Again, exact values of the minimum
are known only in a few small cases.

\medskip

{\it Proof of Ramsey's theorem:} We proceed by induction on $t$, and
for each value of $t$ by joint induction on
$q_{1}$ through $q_{r}$.

Suppose $t=1$.  In this case we are given an $r$-coloring of the
elements of our $n$-element set and asked to find $q_{1}$ elements of
color 1, or $q_{2}$ of color 2, or, etcetera.  Clearly if $n$ is at
least $1 + (q_{1}-1)+(q_{2}-1)+\cdots +(q_{r}-1)$, we can do this by the
pigeonhole principle.  This is our base case for $t$.

Now suppose $t>1$ and assume the theorem holds for coloring
$(t-1)$-subsets.  If any $q_{i}<t$, then a $q_{i}$-subset has no
$t$-subsets and the theorem holds vacuously with $n = q_{i}$.  This is
our base case for the $q_{i}$'s.

For the induction, we assume the theorem holds with any $q_{i}$
replaced by $q_{i}-1$ and accordingly define $n_{i} =
R(q_{1},q_{2},\ldots,q_{i}-1,\ldots,q_{r};t)$, for each $i$.  Then we
assume the theorem holds for $t-1$ (and all $q_{i}$ values), and take
$n = R(n_{1},n_{2},\ldots,n_{r}; t-1) + 1$.

Take an $n$-element set $S$ and pick out one element $v$.  Let an
$r$-coloring of the $t$-subsets of $S$ be given.  To every
$(t-1)$-element subset $X$ of $S\setminus \{v \}$, assign an
``induced'' color by
taking the color given to the $t$-subset $X\cup \{v \}$ of $S$.  Since
$S\setminus \{v \}$ has $n-1 = R(n_{1},n_{2},\ldots,n_{r}; t-1)$
elements, we can find for some color $i$ an $n_{i}$-element subset $T$ of
$S\setminus \{v \}$ in which every $(t-1)$-subset has
induced color $i$.  This means precisely that every $t$-element subset of
$T\cup \{v \}$ which includes $v$ has color $i$ in the originally
given coloring.  Now since $T$ has $n_{i} =
R(q_{1},q_{2},\ldots,q_{i}-1,\ldots,q_{r};t)$ elements, we can either find
a $(q_{i}-1)$-element subset of $T$ of which all $t$-subsets have
color $i$, or for some $j\not =i$ a $q_{j}$-element subset of $T$ of
which all $t$-subsets have color $j$.  In the latter case, we are
done, since we will have found a $j$-monochromatic $q_{j}$-element
subset of $S$.  In the first case, let $U$ be the $(q_{i}-1)$-element
subset of $T$ in which every $t$-element subset has color $i$.
Because of the way we defined $T$, the set $U\cup \{v \}$ will also be
monochromatic of color $i$, and it has $q_{i}$ elements, so we are
done.

\medskip

A good way to be sure you understand the above proof is to follow it
through in the case $t=2$, $r=2$ to see that in that case it is
exactly equivalent to the proof we gave for the asymmetric graph
Ramsey theorem.

The implicit recurrence for Ramsey numbers contained in the proof
shows that 
$$ R(q_{1},q_{2},\ldots,q_{r};t)\leq 1+R(n_{1},\ldots,n_{r};t-1), $$
where $n_{i}$ is the Ramsey number with $q_{i}$ replaced by $q_{i}-1$.
In particular, for two colors, we have
$$ R(p,q;t)\leq 1+R(R(p-1,q;t), R(p,q-1;t);t-1). $$
The upper bounds you get from this for $R(p,q;t)$ grow extremely fast
when $t>2$.  Probably the true values of $R(p,q;t)$ do not grow nearly
as fast, but little information about this is known.

\bigskip

\noindent 3.  A Ramsey application.

\medskip

In this section we will give a nice geometric application of Ramsey's
theorem.  A convex $n$-gon is a plane figure bounded by $n$ vertices
and $n$ straight sides, such that the internal angle at each vertex is
less than $\pi $.  In other words, the figure does not bend inwards at
any vertex.  All triangles (3-gons) are convex.  Below are two
$5$-gons, the first convex, the second not.

\vspace{1in}

\noindent {\it Theorem:} Let $k$ be given.  If $n$ is large enough,
then every set of $n$ points in the plane with no three collinear
contains $k$ points which form the vertices of a convex $k$-gon.

\medskip

{\it Proof:}  First we observe that if $k$ points fail to form a convex $k$-gon
then in fact some four of them fail to form a convex $4$-gon.  To see
this, connect the outermost points of the given $k$ into a convex
$j$-gon, with $j<k$; some point or points of the given $k$ will lie
inside this $j$-gon.  Divide the $j$-gon up into triangles extending
from some vertex, and you find one of these triangles with an interior
point.  The vertices of the triangle, plus the interior point, are four
points which do not form a convex $4$-gon.  Here is an illustration.

\vspace{1in}

Secondly, we observe that among any five points there are four which
form a convex $4$-gon.  To see this, consider the outermost points of
the five.  If there are four or five of them we have our $4$-gon.
Otherwise we have a triangle with two interior points $P$ and $Q$.
Draw the line $PQ$.  Two vertices of the triangle must lie on the same
side of this line.  Then these two vertices, together with $P$ and
$Q$, form a convex $4$-gon.  See picture:

\vspace{1in}

Now we apply Ramsey's theorem.  Given $k$, take $n = R(k,5;4)$.  Given
$n$ points in the plane, we can 2-color their 4-subsets by the rule: a
4-subset is color 1 if it forms a convex 4-gon, color 2 otherwise.
Ramsey's theorem gives us either $k$ points of which every four form a
convex 4-gon (color 1) or else $5$ points of which every four are
non-convex (color 2).  But the latter case is impossible by our second
observation, so we must have the first case.  By our first
observation, the $k$ points in the first case form a convex $k$-gon,
which is what we wanted to show.

\medskip

Again this proof gives numbers $n$ which are far bigger than they need
to be.  In fact, for this problem it is known that you can have
$2^{k-2}$ non-collinear points in the plane with no convex $k$-gon and
it is conjectured that this is the most you can have.  In other words
it is conjectured that $n = 2^{k-2}+1$ (which is far less than
$R(k,5;4)$) is the smallest value that works in the theorem.  For
instance you can have 8 points without a convex 5-gon, but not 9.

\end{document}
