# 2-coloring of R(m,m) with no monochromatic $K_m$

I am working on a pset question on Ramsey numbers and trying to prove the following question:

Let $m \ge 3$ be a positive integer. Construct a red/blue coloring of $K_{(m-1)^2}$ which has no monochromatic $K_m$ (i.e. show that $R_{m,m} \ge (m-1)^{2} + 1$.

Here is my rough draft where I am trying to conceptualize the answer. However, I am new to the subject of graph theory and would appreciate any feedback on how to proceed.

=========================

To construct a $K_{(m - 1)^2}$ that does not have a monochromatic $K_m$, we need to show that there is a 2-coloring of $K_m$ that contains neither a red monochromatic $K_m$, nor a blue monochromatic $K_m$. We will count the colorings of $K_m$ that contain either a red or a blue monochromatic $K_m$. \

Let $S$ be a subset that has $\textit{m}$ vertices and Let $S_2$ be the set of 2-colorings of $K_m$ where the subgraph induced by \textit{S} is either all blue or all red. We can count the number of colorings in $S_2$ as we know that there are two ways to color the edges in the subgraph induced by $\textit{S}$ so that it is monochromatic. Then, we see that the number of 2-colorings containing either a red $K_m$ or a blue $K_m$ corresponds to the cardinality of the union of all the $S_2$'s for all possible subsets $textit{S}$ containing $\textit{m}$ vertices. We know that the union cannot be larger than the sum of the sizes of the sets. Then, the number of 2-colorings containing a monochromatic red or blue $K_m$.... (incomplete)

Then, there must be a 2-coloring of $K_m$ such that it contains no monochromatic coloring of $K_m$ and we can conclude that $R(m,m) \ge (m - 1)^2 + 1$.

• Generally, if the question says to "construct" they mean something like (in this case) "describe how to color the edges explicitly." I haven't thought carefully about your sketch, but it seems like you are trying to prove the lower bound without producing the coloring (not necessarily wrong, but not what is being asked). Commented May 1, 2018 at 14:57
• Thanks for the input. I appreciate it! My next attempt was something like this: Take the vertices of $K_{(m - 1)^2}$ and mark them with the ordered pairs of $(k -1)\ x\ (k-1)$. Consider the vertices $v, u, x, y$ such that $vu \in E$ and $xy \in E$. We see that these two edges are red if $v = x$ and they are blue otherwise. Then, we have constructed a coloring of $K_{(m - 1)^2}$ such that it has no monochromatic $K_m$. === do you think this is how I should approach the question? Commented May 1, 2018 at 14:58
• That seems reasonable except for the use of "we see". You are not being given a coloring or solving for one; you are defining a coloring. Commented May 1, 2018 at 15:21

Here is a (big) hint for finding a coloring. Arrange the vertices in a $(m-1)\times (m-1)$ grid, and color the edges so that every row is a red $K_{m-1}$.
Split the vertices into blocks of size $m-1$, color edges between vertices of the same block red and between vertices of different blocks blue.
If we select $m$ vertices there must be two of different blocks and thus a blue edge, there must also be a block with two or more vertices and thus a red edge.