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 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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

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.