1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – TravisJ May 1 '18 at 14:57
  • $\begingroup$ 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? $\endgroup$ – coder May 1 '18 at 14:58
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov May 1 '18 at 15:21
2
$\begingroup$

You are trying to give a non-constructive proof that a legal coloring exists. Sometimes this is a useful method, but I do not see it working out here. You will probably be better off trying to find an explicit coloring.

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.