Prove that $r_{k+1}(3) \leq (k+1)( r_k(3) - 1) + 2$

Question

I'm tasked to prove that $r_{k+1}(3) \leq (k+1) (r_k(3) - 1) + 2$ and then use the result to come up with an upper bound for $r_n(3)$.

I'd appreciate a bit of a walkthrough, as I've had a hard time with this.

Answer 1

HINT: Suppose that we have an edge coloring of $K_n$ with $k+1$ colors that has no monochromatic triangle. Let $v_0$ be a vertex of the graph, and for $i=1,\ldots,k+1$ let $N_i$ be the set of vertices connected to $v_0$ by an edge of color $i$.

• Show that for each $i$, no two vertices in $N_i$ can be connected by an edge of color $i$. Conclude that the complete subgraph induced by $N_i$ is edge-colored with $k$ colors and has no monochromatic triangle.
• What is the maximum possible number of vertices in $N_i$?
• What is the maximum possible number of neighbors of $v_0$?
• What is the maximum possible value of $n$?

Answer 2

To prove the given inequality, you should recall the proof that $r(3,3)\le 6$, and try a similar strategy. For example, to prove that $r(3,3,3)\le 3\cdot (r(3,3)-1)+2=17$, consider a particular vertex, $v$ in a graph whose edges are colored red, blue and green. Since $v$ is the endpoint of $16$ edges, there must be some color for which $v$ is the endpoint of $\lceil 16/3\rceil =6$ edges of that color. WLOG the color is red, and let $S$ bet the set of vertices joined to $v$ by a red edge. There are then two cases:

• If any two vertices $w$ and $u$ in $S$ are connected by a red edge, then $\{u,v,w\}$ is a red triangle.

• Otherwise, $S$ is only joined together by blue and green edges. Since $6\ge r(3,3)$, there must be either a blue or red triangle.

You need to generalize that argument to all $k$. Instead of using $\lceil 16/3\rceil =6$, you will use $$ \left\lceil (k+1)(r_k(3)-1)+1 \over k+1 \right\rceil=r_k(3) $$

---

For an upper bound on $r_k(3)$, I will use a weaker form of the inequality you were tasked to prove: $$ r_{k+1}(3)\le (k+1)r_k(3)$$ You can apply this repeatedly to get a non-recursive bound on $r_k(3)$. For example, shortening $r_k(3)$ to $r_k$: \begin{align} r_5 &\le 5\cdot r_4 \\&\le 5\cdot 4\cdot r_3 \\&\le 5\cdot 4\cdot 3\cdot r_2 \\&\le 5\cdot 4\cdot 3\cdot 2\cdot r_1 \\&= 5\cdot 4\cdot 3\cdot 2\cdot 3 \\&= 5!\cdot 3 \end{align} Generalizing this pattern, you can prove $r_k(3)\le 3\cdot k!$. You can get a better upper bound by using the full inequality instead of the simplified, but it will be messier.