5
$\begingroup$

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in this case, we're looking for the least positive integer, $n$, such that any red-blue-green coloring of the edges of $K_n$ necessarily admits a monochromatic $K_4$.

Like I said, I've done some searching but turned up absolutely nothing. Have there been any attempts at solving this? i.e. do we have any upper or lower bounds for this?

Tangentially, but related, I also can't find the upper bound for the general multi-color case. That is $R(G_1,G_2,G_3,...,G_n) \le ?$ In the two color case, we have that $R(F,H) \le \binom{s+t-2}{t-1}$ where $s$ and $t$ are the orders of $F$ and $H$, respectively. Is there a combinatorial upper bound for the multi-color case? We know it to exist by Ramsey's theorem, but what is the bound? Or do we not have a closed form bound on this?

EDIT: I found the multi-color case in this question which gives $$R(k_1, \ldots, k_r) \leq 2 - r + \sum_{i=1}^r R(k_1, \ldots, k_{i-1}, k_i - 1, k_{i+1}, \ldots, k_r).$$

So, the question still remains. Is there a better upper bound for $R(4,4,4)$ besides the one given above? Explicitly: $$R(4,4,4)\le 2-3+R(3,4,4)+R(4,3,4)+R(4,4,3)=-1+3\cdot R(3,4,4)\le -1 + 3(79) = 236$$. The result used here is that $R(3,4,4) \le 79$ This is given in the same paper linked in the question I linked previously. This survey paper here

The same paper also gives a lower bound: $R(4,4,4) \ge 128$. I feel like this survey paper would have reflected any recent advancements in either lower or upper bounds for $R(4,4,4)$. So, for now, it looks like the answer to my question is no.

$\endgroup$
2
  • 1
    $\begingroup$ Wouldn't you need R(3, 4, 4) and not R(3, 3, 4) in order to bounded R(4, 4, 4) uing the mentioned theorem? $\endgroup$ – Apple Aug 17 '15 at 20:42
  • $\begingroup$ Oh crud... You're absolutely right. That changes things. I'll work on an edit. Thank you $\endgroup$ – Paddling Ghost Aug 17 '15 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.