1
$\begingroup$

The question is:

Show that there is a two-colouring of the complete graph $K_n$ on $n$ vertices with at most

$\displaystyle {n \choose k} 2^{1-{k \choose 2}}$

monochromatic subgraphs $K_k$.

(Hint: Compute expectation of the number of monochromatic $K_k$. )

I'm confused about what a two-colouring is. Diestel (Graph Theory) says a $k$-colouring is a vertex partition into $k$ independent sets. But for $n \geq 2$ I don't see how you can do this on $K_n$. Can someone work out what "two-colouring" means in this context?

If I assume it means colouring each edge one of two colours randomly, I can prove the result. But I don't see why it should mean this. It's just me doing what's easy.

Thanks!

$\endgroup$
4
  • $\begingroup$ It could mean coloring each $\it vertex$ one of two colors. $\endgroup$
    – Gerry Myerson
    May 26, 2011 at 12:19
  • 1
    $\begingroup$ It means coloring each edge one of two colors. (The other interpretation is clearly false.) $\endgroup$
    – Qiaochu Yuan
    May 26, 2011 at 12:22
  • 1
    $\begingroup$ Why not just clarify with the instructor/professor? $\endgroup$
    – Aryabhata
    May 26, 2011 at 15:18
  • 1
    $\begingroup$ Shouldn't the terminology of the problem then say 2-edge-coloring as the default is usually '... vertex ...' ? $\endgroup$
    – Mitch
    May 26, 2011 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

This appears in the classic probabilistic proof of existence of the Ramsey number $R(k,k)$, due to Erdos, and is indeed a colouring of the edges.

The wiki page on the probabilistic method has the proof here.

$\endgroup$

You must log in to answer this question.

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