Proof of Folkman's lemma.

Question

In combinatorics,in particular,in Ramsey theory,there is a theorem called Folkman's theorem which is as follows:

Given any positive integers $r,k$ there exists $f(r,k)\in \mathbb Z^+$ such that if $\{1,2,...,f(r,k)\}$ is $r$-colored then there exist $1\leq a_1<a_2<...<a_k\leq f(r,k)$ such that $P(a_1,a_2,...,a_k)=\{\sum\limits_{i} c_ia_i: c_i=0,1$ for all $1\leq i\leq k$ and not all $0\}$ is monochromatic.

I am looking for a proof of this theorem.Can someone please provide me a proof or give me a reference where I can find the proof?

Answer 1

There are several proofs of this theorem in Graham, Rothschild, and Spencer's Ramsey Theory which actually appears to be the source that first names this theorem as Folkman's.

Because I feel incapable of leaving it at that, here is my favorite of their proofs.

We begin by proving a lemma: there is a $g(r,k) \in \mathbb Z^+$ such that, in the same setup as Folkman's theorem but coloring up to $g(r,k)$, we can find $a_1, \dots, a_k$ where $P(a_1, \dots, a_k)$ satisfies a weaker condition. Rather than asking for it to be monochromatic, we ask for it to be "striped": the color of a sum $\sum_i c_i a_i$ depends only on $\max\{i : c_i = 1\}$, the largest index of a term $a_i$ included in the sum. (Variants of "striped" colorings appear in many proofs in Ramsey theory.)

We prove the lemma by induction using van der Waerden's theorem. Choose $n$ so that an $r$-coloring of $n$ consecutive integers contains an arithmetic progression of length $g(r,k)$, and let $g(r,k+1) = 2n$. Now, after $r$-coloring $\{1,\dots,2n\}$ arbitrarily:

1. Find such an arithmetic progression $a+d, a+2d, \dots, a+g(r,k)d$ in $\{n+1, \dots, 2n\}$.
2. Color $X = \{1,2,\dots, g(r,k)\}$ by giving $x \in X$ the color of $dx \in \{1,\dots,2n\}$, and find a striped $P(a_1, \dots, a_k)$ in $X$ with respect to this coloring.
3. We claim that $P(da_1, da_2, \dots, da_k, a)$ is striped in the original $r$-coloring of $\{1,\dots,2n\}$. Sums including $a$ are all the same color because they land in the arithmetic progression, and sums not including $a$ are striped by induction.

Also, by construction, $da_1, \dots, da_k$ are all at most $n$, while $a$ is at least $n+1$, ensuring that all $k+1$ values are distinct.

Once we have $g(r,k)$, we can take $f(r,k) = g(r,r(k-1)+1)$ and finish by pigeonhole: we find $\{b_1, \dots, b_k\} \subseteq \{a_1, \dots, a_{r(k-1)+1}\}$ that are the same color. Then their "stripes" in the striped coloring of $P(a_1, \dots, a_{r(k-1)+1})$ are also all the same color, so $P(b_1, \dots, b_k)$ is actually monochromatic.

(Another proof that's shorter but unsatisfying is that Rado's theorem has this theorem as a corollary. This will not make sure that $a_1, \dots, a_k$ are all distinct, but that can be fixed with a bit more work.)