Trying to understand the multicolor Ramsey inequality $R(3,3,3,3)-1\geq(R(3,3)-1)(R(3,3)-1)$.

Question

Notation: $R(3,3,3,3)$ means the Ramsey number of four coloring a complete graph such that any 4-coloring contains a monochromatic $K_3$.

On a superficial level, I understand this to be true. The lower bound of $R(3,3,3,3)$ has been shown to be 51 and $R(3,3)=6$.

$$R(3,3,3,3)-1\geq(51-1)=50\geq(6-1)(6-1)=25.$$

However, I was trying to look for a more intuitive proof that doesn't rely on knowing the lower bound of $R(3,3,3,3)$. I'm thinking of approaching the problem like a lot of other basic Ramsey proofs. Let $n$ be the answer to the LHS of the problem and consider a complete $K_n$ graph that is 2-colored. Pick a vertex $v$ and look at its neighbors...(here is where I get stuck, since I'm not sure how to approach the fact that the RHS is multiplied out...) Any hints would be appreciated.

According to these notes: http://math.mit.edu/~fox/18315/18315notes3.pdf the inequality generalizes $R_k(3,\dots, 3) − 1 ≥ (R_t(3,\dots,3) − 1)(R_{k−t}(3,\dots, 3) − 1)$.

Answer 1

This is a lower bound on a Ramsey number, so we don't want to find a monochromatic $K_3$, but to construct a graph that does not contain a monochromatic $K_3$.

The construction we use is as follows:

1. Start with a red-blue coloring of $K_{R(3,3)-1}$ with no monochromatic $K_3$.
2. Replace every vertex $v_i$ of the red-blue coloring by a set $V_i$ of $R(3,3)-1$ vertices.
3. Between two sets $V_i$ and $V_j$ use the color of edge $v_i v_j$. (That is, whenever $x \in V_i$ and $y \in V_j$, give $xy$ the color that edge $v_iv_j$ had in the original coloring.)
4. Turn each set $V_i$ into a clique and give its edges an orange-purple coloring that has no monochromatic $K_3$.

Here is a somewhat symbolic image of this construction (the thick transparent red and blue lines represent that all the edges between those two parts are the corresponding color).

This is a $4$-coloring of $K_{(R(3,3)-1)(R(3,3)-1)}$ and if we show that it does not have a monochromatic $K_3$ we prove that $R(3,3,3,3) > (R(3,3)-1)(R(3,3)-1)$. Equivalently, we prove that $$R(3,3,3,3)-1 \ge (R(3,3)-1)(R(3,3)-1).$$

So let's verify that. There are three cases to check.

• Three vertices within the same set $V_i$ cannot form a monochromatic $K_3$, because the edges of $V_i$ were given an orange-purple coloring that didn't have monochromatic $K_3$'s.
• Three vertices within three different sets $V_i, V_j, V_k$ cannot form a monochromatic $K_3$, because in our original red-blue coloring the corresponding vertice $v_i, v_j, v_k$ could not have formed a monochromatic $K_3$.
• Three vertices within two different sets (two in $V_i$, one in $V_j$) can't form a monochromatic $K_3$, because the edge between the two vertices in $V_i$ is orange or purple, and the other two edges (crossing from $V_i$ to $V_j$) are red or blue.

---

By the way, this argument works just fine for showing that $$R(a_1,\dots,a_k,b_1,\dots,b_\ell)-1 \ge (R(a_1,\dots,a_k)-1)(R(b_1,\dots,b_\ell)-1)$$ for any $a_1,\dots,a_k,b_1,\dots,b_\ell$. Just use the appropriate coloring on the pieces and you'll be fine.