For the multicolour Ramsey numbers, prove that $R_r(t_1,t_2,...,t_r) \leq r^{1 + \sum_{i=1}^r (t_i - 1)}$.

180 Views Asked by At

I'm trying to imitate the proof below for the symmetric Ramsey numbers $R(s,s) \leq 4^s$, by looking for an appropriately long right-monochromatic sequence in a $r$-color graph on $r^{1 + \sum_{i=1}^r (t_i - 1)}$ vertices. The idea is that, if such a sequence exists, then by the pigeon-hole principle one of the colors will be present in a clique of the required length.

The problem is that I don't know what the "appropriate" length is. If $t = \text{max}(t_1,t_2,...,t_r)$, then certainly a right-monochromatic sequence $v_1,v_2,...,v_{r(t-2)+2}$ of length $r(t-2)+2$ would suffice. However this number is unnecessary large and doesn't work with the number $r^{1 + \sum_{i=1}^r (t_i - 1)}$. I'd like to have some hints if possible.

enter image description here