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$
3
  • $\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
    Commented May 1, 2018 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
    Commented May 1, 2018 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
    Commented May 1, 2018 at 15:21

2 Answers 2

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .