\documentclass{article}
\usepackage{amssymb,graphics}
\input xy
\xyoption{all}

\def\mod#1{\ ({\rm mod\ }#1)}

\begin{document}
\begin{center}
{\Large
MATH 2113/CSCI 2113, Discrete Structures II

Winter 2008

Toby Kenney

\large Homework Sheet 9

Due: Wednesday 2nd April: 1:30 PM}
\end{center}

\begin{list}{}{}

\subsection*{Compulsory questions}

\item[1] (a) Show that if we 3-colour the complete graph on 17 vertices, we get a 
monochromatic triangle.

(b) Is it possible to partition the set $\{1,2,\ldots,16\}$ into 3 sets such that 
no set contains any number which is the sum of two numbers in the same set (possibly the 
same number twice)? [Hint: Given such a partition into the sets $A$, $B$, and $C$, 
take a complete graph on 17 vertices labelled $v_1,v_2,\ldots,v_{17}$, and colour the 
edge $v_iv_j$ red if the difference $|i-j|$ is in $A$, blue if $|i-j|$ is in $B$, and 
green if $|i-j|$ is in $C$. What does a monochromatic triangle mean for this 
colouring?]

\item[2] Suppose we colour each edge of the complete graph on 11 vertices red with 
probability $\frac{1}{3}$ and blue with probability $\frac{2}{3}$ (so it is always 
coloured either red or blue).

(a) What is the expected number of red $K_4$s?

(b) What is the expected number of blue $K_6$s?

(c) Deduce that there is a 2-colouring of the complete graph on 11 vertices without a 
red $K_4$ or a blue $K_6$. [Hint: $2^{14}<3^9$, ${11\choose 4}=330$, ${11\choose 6}=396$, 
$3^6=729$.]

\item[3] (a) Show that if we 2-colour (red and blue) the edges of the complete graph on 10 
vertices, we get either a red triangle or a blue complete graph on 4 vertices.

\subsection*{Bonus Question}

(b) Show that if we 2-colour (red and blue) the edges of the complete graph on 9 
vertices, we get either a red triangle or a blue complete graph on 4 vertices.
[Hint: In part~(a), you probably found a condition on a vertex that would force the 
existence of either a red triangle or a blue $K_4$. With 10 vertices, this condition 
must hold for every vertex. With 9 vertices, it doesn't need to hold for every vertex, 
but suppose it doesn't hold for any vertex, and consider the subgraph consisting of 
just the blue edges.]

\end{list}

\end{document}
