Understanding of Ramsey theorem

Question

Ramsey’s Theorem:

Example: Take a set $S$ of $n$ elements. Construct all $3$-tuples.

Color each $3$-tuple with one of $4$ colors (blue, green, red, orange)

$S = \{1, 2, 3, …, n\}$

$\color\red{\fbox{1,2,3}},\color\green{\fbox{1,2,4}},\color\royalblue{\fbox{1,2,5}},\dots,\color\green{\fbox{4,7,13}}.$

We want a monochromatic subset $T$ of $S$ of size $20.$

$T = \{4, 7, 13, 15, 21, 38, …\},|T| = 20.$

$\color\green{\fbox{4,7,13}},\color\green{\fbox{4,7,15}},\dots$

Ramsey: Such a $T$ always exists if $n$ is large enough.

---

Theorem Statement: For every $m, c,$ and $k$ there exists $n$ such that, if you take a set of size $n$ and color the $m$-tuples with $c$ colors, there will always exist a monochromatic subset of size $k$.

Given:

$m$ – tuple size

$c$ – number of colors

$k$ – desired size of monochromatic subset

There exists: $n$ – size of original set

Proof of Ramsey’s Theorem:

We want to prove the theorem for a certain $(m, c, k).$

We assume, by induction on $m$, that the claim is true for $(m–1, c, k')$ for all $k'.$

Take a set $S$ of size $n,$ for $n$ large enough. Suppose we are given a $c$-coloring $K$ of the $m$-tuples of $S.$

Take $x_1\in S$. Let $T_1=S \setminus \{x_1\}.$ Color the $(m–1)$-tuples of $T_1$ according to their color with $x_1$ in $K.$ Get coloring $K_1.$

By induction assumption, there exists a subset $S_2\subseteq T_1$ all whose $(m–1)$-tuples have the same color in $K_1$.Say all red.

All $m$-tuples “$x_1$ plus $m–1$ elements of $T_1$” are red in $K.$

Color $x_1$ red. $S_2$ is large enough if $S$ is large enough.

Take $x_2\in S_2$. Let $T_2=S_2 \setminus \{x_2\}.$ Define coloring $K_2$ of $(m–1)$-tuples of $T_2$ as before.

By induction assumption, there exists $S_3\subseteq T_2$ all whose $(m–1)$-tuples have the same color in $K_2.$

Say all blue.

Color $x_2$ blue. $S_3$ is large enough if $S_2$ is large enough.

And so on…

Keep going until we have $k$ of the same color.

My question is how many steps are sufficient by PHP(pigeon hole principle)?

Answer 1

Wow, thanks for pointing out this proof, I was just trying to figure it out myself and by coincidence it pops up in my MSE-feed.

The last question seems easy by comparison to finding all the stuff above. If we have a sequence $x_1, x_2, x_3$ that are colored by $c$ colors such that no color appears more then $k-1$ times, then the total number of points in the sequence is at most $(k-1)c$: at most $k-1$ for each of the color and no points that have an as yet unknown color or no color at all.

So, conversely, if we make $(k - 1)c + 1 = kc - c + 1$ steps then some color must appear $k$ times. Of course by sheer luck it could happen earlier, i.e. after $k$ steps, but we are not interested in luck here.

The more interesting question is what an expression for $n$ in terms of $m, k, c$ that, following the logic in the proof, always works (without being optimal perhaps). Is that what you are really after?