Ramsey Numbers involving Cycles, $R(K_3, C_5)$

Question

I've been asked to determine the value of $R(K_3, C_5)$, but I'm having a lot of difficulty putting all the pieces together.

We were given the hint of using $R(3,4) = 9$, and I've tried to apply that, but I don't think my number is "tight" enough.

For example, I wanted to consider $R(3,5)$, because, if a complete graph contains a $K_5$, I know I've got a $C_5$, so I'm done.

Now, I know that; $R(3,5) \le R(2,5) + R(3,4) = 5 + 9 = 14$

So I know that, if I colour a $K_{14}$ in two colours, I'm guaranteed either a $K_3$, or a $K_5$ (and, by extension, a $C_5$), but my question is - can I do any better than this??

Answer 1

Yes, $R(K_3,C_5)= 9$. Below, I've hidden a solution, but you really should try to figure it out yourself now.

First, you'll need to find a coloring of $K_8$ without a red $K_3$ or blue $C_5$.

 

Next, color the edges of $K_9$ in colors red and blue. If there is no blue $K_4$, then by the hint, there is a red triangle and we're done. Otherwise, let the blue $K_4$ be on the vertices $w_1,w_2,w_3,w_4$. Consider the other five vertices $v_1,\ldots, v_5$. At least one of the edges between these is red as otherwise there is a blue $K_5$ and hence blue $C_5$ and we're done. Without loss of generality, say the edge $(v_1,v_2)$ is red.

 

On the other hand, if there are two blue edges from any $v_i$ to $w_1,\ldots, w_4$, then we can form a blue $C_5$ and we're done. So suppose there are at least three red edges from each $v_i$ to $\{w_1,\ldots,w_4\}$. But then in particular a red edge from $v_1$ and a red edge from $v_2$ must be meet at a common vertex $w_j$, and you've found a red triangle.

Answer 2

In $K_8$ let the red graph be $2K_4$ and color all other edges blue, so the blue graph is $K_{4,4}$. The blue graph is bipartite so has no triangle. The components of the red graph are too small to contain a $C_5$. This proves that $R(C_5,K_3)>8$.

Now assume we have a 2-coloring of $G=K_9$ avoiding a red $C_5$ and a blue $K_3$. Assume there is a vertex $v$ with blue degree $\geq5$. Then a $K_5$ at the end of 5 blue edges from $v$ cannot contain any blue edges, so it has a red $C_5$. Contradiction. So every vertex has blue degree less than 5, so red degree at least 4.

Since $R(4,3)=9$, $G$ must contain a red $H=K_4$. A vertex $v\in G-H$ can have at most one red edge to $H$ (or otherwise two elements in $H$ have a common red neighbour, which would produce a red $C_5$). So every vertex in $G-H$ still has red degree at least 3 in $G-H$. Since $G-H$ has only 5 vertices, we can use Ore's theorem to find a Hamiltonian cycle (i.e. a $C_5$) in the red graph, contradiction. So $R(C_5,K_3)\leq 9$.