\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2011/11/16 before class

\begin{center}
{\LARGE\bf Homework 7}
\end{center}

\begin{hw}[The Chv\'atal graph] The graph in Figure \ref{fig.chvatal} is due to
Va\v{s}ek Chv\'atal (1970). It is 4-regular and has girth 4.
Prove that it is 4-colourable.
\end{hw}

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=2.0in]{chvatal.eps}
  \end{center}

  \caption{\small The Chv\'atal graph.}
  \label{fig.chvatal}
\end{figure}


\begin{hw}
Define the graph $G_2$ to be a simple edge. And when $G_k$ is defined,
we define $G_{k+1}$ as follows. Suppose $V(G_k) = \{a_1, a_2, \cdots, a_t\}$,
we add $t+1$ new points,
\[V(G_{k+1}) = V(G_k) \cup \{b_1, b_2, ..., b_t, x\}.
\]
And for the edges, we keep all the edges in $G_k$; for each $b_i$,
connect it with all the neighbors of $a_i$ in $G_k$; and finally
connect $x$ to every $b_i$.

(a) Draw the graphs $G_3$ and $G_4$.

(b) How many vertices are there in $G_k$?

(c) Show that $G_k$ is triangle-free for any $k$.

(d) Suppose $G_{k+1}$ has a proper colouring $s:V(G_{k+1}) \rightarrow [k]$ and
$s(x) = k$. Show that we can modify $s$ to another colouring $s'$ where
$s'$ is proper on the $\{a_i\}$'s using only $[k-1]$.
(This means $G_k$ is $k-1$ colourable, and by induction,
we can prove $\chi(G_k) = k$ for all $k$.)
\end{hw}

\begin{hw} Let $A$ be a set of $2r+1$ points
\[ A = \{a_1, ..., a_r, b_1, ..., b_r, c\}. \]
Uniformly pick a random permutation $\sigma$ of $A$.
Define the random variables
\[ x := |\{ a_i | a_i \prec_\sigma c\}|,\]
\[ y := |\{ b_i | b_i \prec_\sigma c\}|.\]
Let $0 \leq p \leq 1$ be fixed.

(a) When $r = 1$ and $r = 2$, compute $\expe_\sigma[(1+p)^x (1-p)^y]$.

(b) Prove that $\expe_\sigma[(1+p)^x (1-p)^y] \leq 1$. (Hint:
Let $c_i$ be the number of elements in $\{a_i, b_i\}$ that are
before $c$, $(c_1, ..., c_r)$ is a sequence of 0-1-2 of length
$r$. Partition all the outcomes by conditioning on such sequences.)
\end{hw}

\end{document}
