What's the Ramsey number of $r(K_3, P_m)$?

Question

As in the question, what's the Ramsey number of $r(K_3, P_m)$, where $K_3$ is a complete graph with 3 vertices and $P_m$ is a tree with width 1 (a "line")?

I am watching https://www.youtube.com/watch?v=FCHTHcP1EIc

but Rob only explains in Portuguese, I could not understand....

Thanks in advance.

Answer 1

The value you want is $r(K_3, P_m) = 2m-1$.

On the one hand, we can color $K_{2m-2}$ as follows: divide the graph into two parts of size $m-1$, color the edges within a part blue (the color we want a $P_m$ in) and color the crossing edges red (the color we want a $K_3$ in).

Then there is no blue $P_m$ because a blue path cannot leave the half of the graph it started in, and there are only $m-1$ vertices in that half. There is no red $K_3$ because the red edges form a bipartite graph $K_{m-1,m-1}$, which has no odd cycles.

On the other hand, suppose that we are coloring $K_{2m-1}$. We start at an arbitrary vertex $v_1$ and try to build a blue $P_m$, one step at a time. To extend the path, we ask: is there a blue edge from the last vertex $v_k$ in our path that goes to a vertex we haven't seen yet?

If so, we just make our blue path one vertex longer. If not, then suppose our blue path is $k \le m-1$ vertices long (if $k \ge m$, we'd be done). Then all edges from $v_k$ to the other vertices are red, and there are $(2m-1)-k$ other vertices, which is at least $(2m-1)-(m-1) = m$.

If any of those vertices have a red edge between them, then together with $v_k$ they form a red $K_3$. If all edges between those vertices are blue, then it's trivial to find a blue $P_m$ among them (since there are at least $m$ of those vertices).

---

This argument generalizes easily:

1. Instead of a $P_m$, we could have been looking for any specific tree on $m$ vertices, and both the lower and upper bound work without modification. It's just that to "grow" the tree, we don't necessarily start with the last vertex, but we do have some specific vertex we can start from.
2. Instead of a $K_3$, we could have been looking for a larger clique $K_t$. Then we can color $K_{(t-1)(m-1)}$ by dividing it into $t-1$ parts of size $m-1$, coloring all edges within a part blue and the crossing edges red. We can find a red $K_t$ or blue tree $T_m$ in $K_{(t-1)(m-1)+1}$ by the same argument as before, except that the last step (where all edges between $m$ vertices were forced to be blue) is now an induction step (where we have at least $r(K_{t-1}, P_m)$ edges left).