Let $q_1$, $q_2$, ..., $q_k$, t be positive integers, where $q_1$≥t, $q_2$≥t, ..., $q_k$≥t. Let m be the largest of $q_1$, $q_2$, ..., $q_k$. Show that
$r_t$(m, m, ..., m) ≥ $r_t$($q_1$, $q_2$, ..., $q_k$).
Conclude that to prove Ramsey's theorem, it is enough to prove it in the case that $q_1$ = $q_2$ = ... = $q_k$.
This problem is from Brualdi's Introductory Combinatorics p.85.
I have a strong intution to apply induction on t, and I got a good grasp on the case t=1 (in which case the problem is reduced to pigeonhole principle).
But, I'm stuck with the inference from t=n-1 to t=n. How to proceed here?
Thanks.
Notation : By $r_t$(q), Brualdi means the Ramsey number of $K^t_q$, denoting the collection of all subsets of t elements of a set of q elements. (Thus, by this notation, $K^2_3$ denotes the complete graph of triangle.)
You don’t need induction. Let $q_1,\ldots,q_k\ge t$, let $$n=r_t(\underbrace{m,\ldots,m}_k)\;,$$ and let $c$ be a $k$-coloring of $[n]=\{1,\ldots,n\}$. Then there is an $S\subset[n]$ of cardinality $m$ that is homogeneous for $c$. Suppose that $S$ is homogeneous for color $i$, where $1\le i\le k$. Let $S_0$ be any subset of $S$ of cardinality $q_i$; clearly $S_0$ is homogeneous for $c$ for color $i$.