# Ramsey Numbers and Graphs

The Ramsey number $R(G,H)$ of two graphs $G$ and $H$ is the smallest value $n$ such that any 2-coloring of the edges of $K_n$ contains either a red copy of $G$ or a blue copy of $H$ .

The chromatic number $X(G)$ of a graph $G$ is the smallest number $k$ such that $G$ is k-colorable. This means that:

• We use $k$ colors to color the nodes of $G$.
• Adjacent nodes in $G$ have different colors.

$C(H)$ = the order (that is, number of nodes) of the largest connected component of a graph $H$.

This is a relation between $X(G)$ and $C(H)$ :

$$R(G,H)\ge(X(G)- 1)(C(H) -1) + 1$$

Find $R({P_3,P_3})$, $R({P_3,C_4})$, $R({C_4,C_4})$ . Also, I need to prove that $R({K_{1,3},K_{1,3}})=6$ and $R({2K_3,K_3})=8$ .

I haven't tried anything yet hence I don't know where to start, any help is appreciated.

• Try coloring $K_n$ for small $n$? – Mario Carneiro Dec 18 '12 at 9:31
• How will that help me to find $R(P_3,P_3)$ and others..? – Dream Box Dec 18 '12 at 9:37
• @Dream Box : The definition concerns $2$-colorings of the edges of $K_n$, so I guess it's a good place to start. – Patrick Da Silva Dec 18 '12 at 9:40
• I'll admit that remark was rather tongue-in-cheek, but depending on the numbers involved, you may be able to produce all 2-colorings of $K_n$ and keep going up in $n$ until every 2-coloring has a copy of $G$ or of $H$. The combinatorics involved may make this prohibitive, though, I'm not sure at what point. – Mario Carneiro Dec 18 '12 at 9:41
• I guess that for the small graphs $G$ and $H$ it's easier. I have answered a suggestion for those. – Patrick Da Silva Dec 18 '12 at 9:49

I will give you the idea for $R(P_3, P_3)$. Clearly $n \ge 3$ because your graph $K_n$ must have a subgraph isomorphic to $P_3$ and there is no such subgraph in $K_3$.

What about $n = 4$? Try all the colorings of $K_4$. Is there one that doesn't fit the definition? (I have actually verified that $R(P_3,P_3) = 4$.)

For the other ones, use the identity on $R(G,H)$ to get the smallest $n$ on which you can start checking if $R(G,H) = n$.

Hope that helps.

• When you say try all the colorings of $K_4$ what do you mean? I know that the number of colors that can be used in a $K$ graph is $n$ so what am I missing here? – Dream Box Dec 18 '12 at 9:58
• To show that a Ramsey number $R(G, H) = n$, you need to show that every $2$-coloring of the edges of $K_n$ contains either a copy of $G$ with all its edges of color $1$ or a copy of $H$ with all its edges of color $2$. – Andrew Uzzell Dec 18 '12 at 10:29
• Well how is $R(P_3,P_3)=4$ when there are at least 4 colors to color $K_4$? $P_3$ is colored in 2 colors, yet there isn't any subgraph in $K_4$ that is colored with the same color twice? – Dream Box Dec 18 '12 at 10:53
• The coloring is an edge-coloring, not a vertex-coloring. Also, it need not be (and almost never is) a proper coloring. – Andrew Uzzell Dec 18 '12 at 11:54
• @Dream Box : You only need to find one $n$, because $K_{n+1}$ has $K_n$ as a subgraph, so if $K_n$ satisfies the property, so does $K_{n+1}$. I don't want to do the drawing here, it would take a while... so please do an edge-2-coloring of $K_4$ and see what happens. If you really need it I could try plotting one here. – Patrick Da Silva Dec 18 '12 at 18:04