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.
[Math] Upper bound on multicolor ramsey number
coloringcombinatoricsgraph theoryramsey-theory
Best Answer
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!$.