Upper bound for 3-color Ramsey numbers

167 Views Asked by At

I'm trying to prove the following inequality for 3-color Ramsey numbers: $$R(s,t,g) \le R(s-1,t,g)+R(s,t-1,g)+R(s,t,g-1)$$ for $s,t,g > 2$.

My attempt: (the "proof" below is not really a proof, just a bunch of ideas. I denoted all holes in the logic by putting comments inside [square brackets]).

Define $R_1=R(s-1,t,g), R_2=(s,t-1,g), R_3=R(s,t,g-1)$, and let $n=R_1+R_2+R_3-1$. We want to show that $R(s,t,g) \le n$, i.e. that $K_n$ contains a red copy of $K_s$ or a blue copy of $K_t$ or a green copy of $K_g$ as a subgraph. Fix a vertex $v$ in $K_n$ and consider an edge 3-coloring of $K_n$. The pigeonhole principle tells us that there are at least $\lceil (n-1)/3 \rceil$ edges in one color, say red [I don't know what to do with this fact].

Then I tried something along these lines: Take $R_1$ vertices other than $v$ [not sure if there are enough of them in order for this to work] $u_1,...,u_{R_1}$. Consider a graph $K_{R_1}$ on vertices $u_1,...,u_{R_1}$. If this graph contains a red clique $K_{s-1}$, then together with $v$, we get a red clique $R_s$ [there would need to be at least $s-1$ vertices $u_j$ which are joined to $v$ by a red edge]. If not, then the graph contains either a blue clique on $t$ vertices or a green clique on $g$ vertices.

Am I on the right track? How should I proceed from here and how do I feel the missing parts?