# What is the upper bound of $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$times}$?

Just some context: $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$times}\leq n$, means that any colouring of a complete graph, $k_n$, on $n$ vertices or more with $k$ colours must contain a monochromatic triangle.

Claim: $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$times} \leq 3k!$

Proof: Consider the minimum number of monochromatic edges connected to an arbitrary vertex, $V$. At least $\big\lceil{\frac{3k!-1}{k}}\big\rceil$ edges will be monochromatic. $\big\lceil{\frac{3k!-1}{k}}\big\rceil$ =$\frac{3k!}{k}$ when $k>1$. Therefore, vertex $V$ must be connected to $3(k-1)!$ monochromatic edges.

By trying to avoid a monochromatic triangle of color $k_1$, we will be forced into creating a monochromatic triangle of color {$k_2$, $k_3$, $\ldots$, or $k_i$}. If we connected any of the vertices $\{1,2,3, \ldots, 3(k-1)!\}$ with a blue edge, a blue monochromatic triangle would be formed, to avoid this, the remaining $3(k-1)!$ vertices must be colour with the remaining $k-1$ colours.

We can then consider a subgraph of the remaining vertices $\{1,2,3,\ldots,3(k-1)!\}$ and colour it with the remaining $k-1$ colours. We can focus on a new vertex, $V'$, within the subgraph.

Vertex $V'$ will be connected to at least $\displaystyle{\frac{3(k-1)!}{k-1}}$ monochromatic edges. Which equals $3(k-2)!$ edges.

We can continue this process until we consider the subgraph of remaining vertices $3(k-(k-1))!$ and colour it with the remaining $k-(k-1)$ colours. This means that this final subgraph has 3 vertices and has to be coloured with 1 colour. Therefore, a monochromatic triangle is unavoidable. Therefore, $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$times} \leq 3k!$.

I managed to get it down to $3k!$, I was wondering if anyone had better approximations?

• Not really. This is an open problem which deserves to be better known, I think. You have a small improvement using the fact $R(3,3,3)=17$, and if you compute more this can be improved, but it should not be close to the true answer. Apr 14, 2017 at 16:36
• If I recall correctly one can get it down to around $ek!$ by essentially the same argument, just being a bit more careful with the recursion (i.e. keeping track of the $-1$'s floating around at every step). But that's only a constant factor, so probably not too interesting.
– Nate
Apr 14, 2017 at 18:38
• This is not directly related to the question, but there just appeared a preprint with a bunch of new bounds for various Ramsey numbers arxiv.org/abs/1704.03592 Apr 15, 2017 at 1:54

All questions about Ramsey numbers for small graphs should be first checked in Staszek Radziszowki's amazing frequently updated survey. On page 40 we find the upper bound $(e-\frac16)k!+1\approx 2.55 k!$, proved by Xu Xiaodong, Xie Zheng and Chen Zhi in a paper published in Chinese.
• Which, though, probably should still not be close to the right answer (I think it's generally believed the answer is $o(k!)$, and rather substantially so). Apr 15, 2017 at 13:43