9
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – user36212
    Apr 14, 2017 at 16:36
  • 4
    $\begingroup$ 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. $\endgroup$
    – Nate
    Apr 14, 2017 at 18:38
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 15, 2017 at 1:54

1 Answer 1

16
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$
    – user36212
    Apr 15, 2017 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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