8
$\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$
  • 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 '17 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 '17 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$ – Max Alekseyev Apr 15 '17 at 1:54
13
$\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$
  • $\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 '17 at 13:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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