The Ramsey number $r(t,t,q)$ with $q\geq t$

Question

Let q and t be positive integers with $q\geq t$. Determine the Ramsey number $r_t(t,t,q)$. This is from the book Introductory Combinatorics by Brualdi, and in the back it says the answer is q without any explanation. I found that odd since r(3,3,3)=17, what am I missing or is there a typo somewhere?

Answer 1

The expressions $r_t(t,t,q)$ and $r(t,t,q)$ have different meanings. In the latter, you are coloring edges of a graph (that is, two-sized sets). In the former, you are coloring $t$-sized sets.

The number $r_t(t,t,q)$ is the smallest number $n$ that ensures that if we color the $t$-sized subsets of $n$ with $3$ colors $1,2,3$, we either have a monochromatic set of size $t$ in color $1$ or in color $2$, or else we have a monochromatic set of size $q$ in color $3$.

To show that this is $q$, suppose first we color the $t$-sized subsets of a set of size $q$ with $3$ colors $1,2,3$. If any $t$-sized set has color $1$ or $2$, we are done: That is our monochromatic set. The alternative is that all $t$-sized sets have color $3$. Then we have a monochromatic set of size $q$ for color $3$. This shows that $r_t(t,t,q)\le q$. To show the equality, simply color each $t$-sized subset of a set of size $q-1$ in color $3$. You don't have monochromatic sets in the first two colors, and no monochromatic set for the third color has size $t$, so $r(t,t,q)\ge q$.

In contrast, to compute $r(t,t,q)$ you must color sets of size $2$. If $t>2$, you are not automatically guaranteed a monochromatic set of size $t$ for color $1$ or $2$ simply because either color is used at least once. For example, if you color each edge of a triangle a different color, you have monochromatic sets of size $2$, but no monochromatic set of size $3$, so $r(3,3,3)>3=r_3(3,3,3)$.

The issue is simply that $\binom{t}{t}=1$ while $\binom{t}2>1$ for $t>1$. Recall that $\binom{a}{t}$ counts the number of $t$-sized subsets of a set of size $a$. When looking at $r_t(a,\dots)$, all these sets would have to have the same color to ensure a monochromatic set of size $a$ in the first color.