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.

  • $\begingroup$ What does it mean for something to "exist finitely"? Where are you getting this phrase? $\endgroup$ – Morgan Rodgers Jul 23 '18 at 5:25
  • $\begingroup$ 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? $\endgroup$ – Dbchatto67 Jul 23 '18 at 5:27

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).

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Dbchatto67 Jul 23 '18 at 6:04
  • $\begingroup$ 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. $\endgroup$ – Dbchatto67 Jul 23 '18 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.