Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $q_{1},\, q_{2}, \ldots, q_{k},t$ be positive integers, where $q_{1}\geq t, q_{2}\geq t, \ldots, q_{k}\geq t$. Let $m$ be the largest of $q_{1},q_{2}, \ldots, q_{k}$.

Show that $r_{t}(m,m,\ldots,m)\geq r_{t}(q_{1},q_{2}, \ldots,q_{k})$

Conclude that to prove Ramsey's theorem, it is enough to prove it in the case that $q_{1}=q_{2}= \ldots =q_{k}.$

If I understand correctly, the LHS means:

Assume we have $n$ objects and $k$ colors and we color subsets of $t$ elements. then if $n=r_{t}(m,m, \ldots, m)$ means that there must be $m$ such subsets of the same color. Am I right? Any help is apreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Here's one way to look at it:

Let $r_1:=r_t(m,m,\cdots m)$ and $r_2=r_t(q_1,q_2,\cdots q_k)$.

If we $k$-color the $t$-order subsets of $\{1,2,\cdots r_1\}$ then by the definition of $r_1$ we are guaranteed that a $m$-order subset of $\{1,2,\cdots r_1\}$ exists such that its $t$-order subsets will all be of the same color (say color $i$).

Clearly, then since $m\ge q_i$ any $q_i$ elements in that $m$-subset constitute a $q_i$-order subset of $\{1,2,\cdots r_1\}$ such that its $t$-order subsets are all of the same color. In this way we see that for any coloring of the first $r_1$ numbers, there is such a subset for some $i$. Define this property as property $R$. Hence $r_1$ satisfies property $R$. By definition $r_2$ is the least such positive number so that property $R$ holds, and hence we have $r_2\le r_1$.

Note that we do not use the fact that $m=max\{q_1,\cdots q_k\}$; we only require the weaker condition that $m\ge q_i\forall i$.

Now by the well ordering principle if one could show that there is a non-empty subset of $\mathbb{N}$ satisfying property $R$, then it will have a least element. So it is required to prove only the existence of $r_1$ to establish the existence of $r_2$. Further, once we have established that numbers of the kind $r_1$ (call them diagonal ramsey numbers) exist, the proof shows that any $r_t(q_1,\cdots q_k)$ exists. So the existence of all diagonal numbers, i.e. the case when all arguments are equal, is the only thing that requires a proof.

For another interpretation of the statement of Ramsey's theorem through hypergraphs and a proof for the diagonal case see my blog post here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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