Ramsey coloring of $K_{13}$

Question

Arrange the vertices of $K_{13}$ in such a way that they form a regular $13$-gon. Color the edges (which are now either edges or diagonals of the 13-gon) in read and blue, where an edge is colored red if and only if it is either an edge of the $13$-gon or a diagonal such that 4 vertices lie on one of the its sides and 7 vertices on the other side. Use this coloring to show that $R(3,5) \geq 14$. Then use the lemma showing bounds for the Ramsey numbers to prove that $R(3,5) = 14$.

Any ideas? I'm already having difficulty imaging the situation and the problem.

Answer 1

Using the inequality lemma you have already proved that $R(3,5) \leq 14$, so if you find a red-blue coloring for $k_{13}$ such that there is no red $k_ 3$ and no blue $k_5$ you would have proven that $R(3,5) > 13$ which means that $R(3,5)=14$

The required coloring is described in your exercise:

An edge is colored red if and only if it is either an edge of the 13-gon or a diagonal such that 4 vertices lie on one of its sides and 7 vertices on the other side

and of course the rest is blue.

so first you draw the red 13-gon and then you add from each vertex a diagonal such that it has 4 vertices on one side and 7 on the other. Something like this:

finally you get :

this is the red edges in the coloring and which they do not contain a $k_3$

now you continue your coloring, by connecting each vertex to the remaining 10 vertices with the color blue, which will also not contain a blue $k_5$

One note though: if your textbook have not proved that $R(3,4)=9$ before, then you are required to, and this can be done using the same idea:

1. first use the lemma and you get $R(3,4) \leq R(2,4)+R(3,3)=4+6=10$
2. find a red-blue coloring for $k_8$ such that there is no red $k_3$ nor a blue $k_4$
3. prove that there is always in a red-blue coloring of $k_9$ either a red $k_3$ or a blue $k_4$