# Understanding the proof of the Generalized Ramsey's theorem.

Generalized Ramsey's Theorem $:$

Given positive integers $k,r,l_1,l_2, \cdots, l_r$ $\exists$ a positive integer $n=R_{*}(k,r,l_1,l_2, \cdots, l_r)$ such that for any $r$-coloring of the $k$-subsets of $[n]$ with colors $c_1,c_2, \cdots, c_r$ $\exists$ some $i \in \{1,2, \cdots, r \}$ for which $\exists$ an $l_i$-subset $L$ of $[n]$ such that the $k$-subsets of $L$ are monochromatic with color $c_i$.

Proof $:$

When $k=1$ it is nothing but Generalized pigeon-hole principle. Let $k>1$ and assume that $R_{*} (k-1,r, l_1,l_2, \cdots, l_r)$ defined for all $l_i$'s. For any $k$ if $l_i=k$ for all $i$ then again the result follows trivially.

Assume that the numbers $a_i= R_{*} (k,r,l_1,l_2, \cdots, l_{i-1},l_i-1,l_{i+1}, \cdots, l_r)$ are defined for $i=1,2, \cdots, r$. Let $n=1+R_{*}(k-1,r,a_1,a_2, \cdots, a_r)$. Let an $r$-coloring $\psi$ of the $k$-subsets of $[n]$ with colors $c_1,c_2, \cdots, c_r$ are given. Choose $m \in [n]$ and let $Y=[n] \setminus \{m \}$.

Give an induced $r$-coloring $\psi^*$ of the $(k-1)$-subsets $S$ of $Y$ as follows $:$

$\psi^*(S) = c_i^*$ $\Leftrightarrow \psi (S \cup \{m \}) = c_i$.

By the definition of $n$ for some $i$ $\exists$ $A_i \subset [n] \setminus \{m \}$ such that $|A_i|=a_i$ and all the $(k-1)$-subsets of $A_i$ have the same color $c_i^*$. Now the set $A_i$ will contain either a set $X$ of size $l_j$ all of whose $k$-subsets have the same color $c_j$ for $j \neq i$ or a set $X$ of size $l_i-1$ all of whose $k$-subsets have the same color $c_i$.

For the first case we are through. For the second case given $K \subset X \cup \{m \}$ with $|K|=k$. If $m \notin K$ then by the above discussion it is clear that $K$ is of color $c_i$. If $m \in K$ then $K \setminus \{m \}$ being a $(k-1)$-subset of $A_i$ is of color $c_i^*$ and hence by the definition of the induced coloring $K$ is of color $c_i$. This completes the proof.■

I don't understand the induction hypothesis and inductive step used in this proof. How do we assume that the numbers $a_i= R_{*} (k,r,l_1,l_2, \cdots, l_{i-1},l_i-1,l_{i+1}, \cdots, l_r)$ are defined for $i=1,2, \cdots, r$. Also how do we know $n$ defined by $n=1+R_{*}(k-1,R,a_1,a_2, \cdots, a_r)$ exists finitely. The theorem is not clear to me enough. Also if some $l_i=k$ then are we not through? Why do we need this for all $l_i$? Please help me in this regard.

Thank you very much.

• What does it mean for something to "exist finitely"? Where are you getting this phrase? – Morgan Rodgers Jul 23 '18 at 5:25
• I mean to say that how do I know there exists $n \in \Bbb N$ for which $n=1+R_{*}(k-1,R,a_1,a_2, \cdots, a_r)$ will be satisfied? – Dbchatto67 Jul 23 '18 at 5:27

## 1 Answer

I believe that it is assumed that $r$ is fixed and arbitrary. Fixing $r$, we will show by induction on $k$ that this theorem holds. It is easily shown for $k=1$, then you (IH) assume $R_{*}(k-1,\ldots)$ is defined for all choices of the other parameters.

Since $R_{*}(k-1,r,a_{1},\ldots,a_{r})$ is defined (in $\mathbb{N})$, certainly $1+$ this number will be finite.

Now considering $R_{*}(k, r, \ldots)$, the theorem is trivially true if any of the $l_{i} < k \leq 2$, so certainly there will be a choice of $l_{1}, \ldots, l_{r}$ such that $R_{*}(k,r,l_{1}, \ldots, l_{i-1},\ldots, l_{r})$ is finite (taking all $l_{i} = k$ gives one such example).

• Why is $R_{*} (k-1,r,a_1,a_2, \cdots, a_r)$ defined? Also what do you mean by $r$ is fixed and arbitrary? – Dbchatto67 Jul 23 '18 at 6:04
• Would you please give me some link where I can find an alternative proof of the same? This proof creates lots of problems to me. – Dbchatto67 Jul 23 '18 at 6:08