1
$\begingroup$

Let $k \geq 3$ and $n = (k−1)^2$. Give an explicit 2-coloring of the edges of $K_n$ that does not have a monochromatic $K_k$.

My thoughts were to partition the graph into k-1 subgraphs each with k-1 many vertices and color all edges connecting vertices of the same subgraph as red, and all edges connecting vertices of different subgraphs blue.

Does this work?

$\endgroup$
1
  • $\begingroup$ It does work. It's clear from construction that there is no red $K_{k}$ but I would explain more carefully why there is no blue $K_{k}$. Specifically, pick (any) $k$ vertices and use the pigeonhole principle to prove that two of them must lie in the same subgraph, ie their are connected by a red edge; hence the $k$ vertices do not form a blue $K_{k}$. (Note that in order to take $k$ vertices, you need $k\leq(k-1)^2$; that's why we need $k\geq 3$) $\endgroup$
    – Colorblind97
    Commented Feb 28, 2020 at 16:17

1 Answer 1

Reset to default
1
$\begingroup$

Index the $n=(k-1)^2$ by the ordered pairs $(i,j)$ where $i,j=1,2,\cdots,k-1$. Now join the pairs $(i,j)$ to $(i,j')$ with red edges and also join the pairs $(i,j)$ to $(i',j)$ with red edges. join all other edges with blue edges.

Claim there will not be any monochromatic $K_k$. It is reasonably easy to see that there will be lots of red $K_{k-1}$'s but any further element will cause a blue edge to be included, so there are no red $K_k$'s.

Now a blue $K_k$ will need to be $k$ vertices $(i_1,j_1),\cdots,(i_k,j_k)$ where all the $i$'s are distinct which is impossible (by the pigeon hole principle), so there are no blue $K_k$'s.

$\endgroup$

You must log in to answer this question.

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