1
$\begingroup$

I have an assignment question for an intro course in Graph theory where we have to show that $R_k (3) := R(3_1,...,3_k) \leq 3k!$. Since this is an intro course we do not know much about ramsey numbers. I have the classic upper bound on 2 color ramsey numbers $R(k,l) \leq R(k-1,l) + R(l,k-1)$ and also the proof by induction that the multicolor Ramsey number exists for all positive integers $s_1,...,s_k$ by induction : $R_k(s_1,...,s_k) \leq R_{k-1}(R_2(s_1,s_2),s_3,\ldots,s_k)$. I think the same kind of induction should be used but I don't really know how to make that upper bound become a product.

$\endgroup$
2
$\begingroup$

This exercise also belongs to introduction and induction. To obtain an upper bound for $R_k(3)$ put $n=R_k(3)-1$ and consider a complete graph $K_n$ with edges colored in colors $\{1,\dots, k\}$ without monochromatic triangles. Pick an arbitrary vertex $v_0$ of the set $V$ of vertices of the graph $K_n$. Then we obtain a partition $V\setminus \{v_0\}=V_1\cup\dots\cup V_k$, where $V_i=\{v\in V: (v_0,v)$ has color $k\}$. Since edges of each $V_i$ cannot be colored by a color $i$, $|V_i|\le R_{k-1}(3)-1$. Thus $n\le 1+k(R_{k-1}(3)-1)$ and $R_{k}(3)\le kR_{k-1}(3)-k+2$. Since $R_2(3)=6=2\cdot 2!$, by induction we obtain $R_k(3)\le 3\cdot k!$.

$\endgroup$
2
  • $\begingroup$ Why the condition of not having a monochromatic triangle? $\endgroup$ – ARi Oct 13 '17 at 15:15
  • 1
    $\begingroup$ @ARi By the definition of a Ramsey number $R_k(3)$ as a smallest number $n’$ such that any edge-coloring in $k$ colors of a complete graph $K_{n’}$ has a monochromatic triangle. $\endgroup$ – Alex Ravsky Oct 14 '17 at 12:35

Your Answer

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

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