Ramsey numbers: if $s_1 \leq s_2$ then $R(s_1,t)\leq R(s_2,t)$

107 Views Asked by At

I'm doing this little homework assignment on Ramsey numbers, the question is: Show that $$s_1 \leq s_2 \Rightarrow R(s_1,t)\leq R(s_2,t).$$

I've tried classifying it into these four cases:

  1. The graph on $R(s_1,t)$ vertices has a clique of size $s_1$, and the graph on $R(s_2,t)$ vertices has a clique of size $s_2$,

  2. Both graphs have an independent set of size $t$,

  3. The graph on $R(s_1,t)$ vertices has a clique of size $s_1$, and the graph on $R(s_2,t)$ vertices has an independent set of size $t$,

  4. The graph on $R(s_1,t)$ vertices has an independent set size $t$, and the graph on $R(s_2,t)$ vertices has a clique of size $s_2$.

Cases 1 and 2 seem trivial but since we can't compare $t$ to $s_1$ and $s_2$, I have absolutely no idea how to handle cases 3 and 4. Or was considering four cases a brilliant idea?

1

There are 1 best solutions below

0
On

Hint: As bof stated in his response, a ton of casework isn't necessary. Let's just unpack the definitions and think carefully about what's going on.

Suppose $s_1 \leq s_2$ and consider $n = R(s_2, t)$. In terms of edge colorings, this means we can arbitrarily $2$-color (red/blue say) the edges of $K_n$ and be guaranteed to find a complete red subgraph on $t$ vertices or a complete blue subgraph on $s_2$ vertices.

If we can find one on $t$ vertices, we are done. If we can find one on $s_2$ vertices, then note that $K_{s_1}$ can be realized as a subgraph of $K_{s_2}$ if $s_1 \leq s_2$.

Carefully following the definition of $R( \bullet, \bullet)$, can you deduce from this that $R(s_1, t) \leq R(s_2, t)$?