\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\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/09 before class

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

\begin{hw}
Consider the cycle $C_4 = (V, E)$, where $V = \{a, b, c, d\}$, and
$E = \{ab, bc, cd, da\}$.
We randomly color each of the 4 edges as red with probability $1/3$, and blue with
probability $2/3$. For each outcome, let $R = (V, \{e \in E : e \text{ is red}\})$
and $B = (V, \{e\in E : e \text{ is blue}\})$.

(a) The probability space contains 16 possible outcomes,
for each of the resulting graph, draw it, and compute it's probability mass.
(As usual, I don't care if you draw red edge with a red pen or not.)

(b) Define the random variable $X$ to be the number of connected components
in $R$, what is $\expe(X)$?

(c) Define the random variable $Y$ to be the indicator random variable for the event
``$B$ is bipartite''. What is $\expe(Y)$?

(d) Define the event $E := $ both $R$ and $B$ are disconnected. What is $\prob(E)$?

\end{hw}

\begin{hw}
For any positive integer $n$, there is a tournament on $[n]$ where the number of directed
Hamilton paths (a directed path of length $n-1$ that visits each vertex exactly once) is
at least $n! / 2^{n-1}$. (This is probably the first use of probabilistic method. Szele 1943.)
\end{hw}

\begin{hw}
Prove the following by induction:
Let $v_1, v_2, ..., v_n$ be $n$ vectors in $\br^n$ and $|v_i| = 1$ for all $i$. Then
there exists $\epsilon_1, ..., \epsilon_n$ such that each $\epsilon_i$ is either $1$ or $-1$,
and $|\sum_{i=1}^n \epsilon_i v_i| \leq \sqrt{n}$.
\end{hw}

\begin{hw}
Prove the proposition in the previous problem using probabilistic method. (You may follow
this line: Pick each $\epsilon_i$ randomly, let $v = \sum_i \epsilon_i v_i$ and define the random variable
\[X = | v |^2 = (v, v),\]
where $(,)$ is the inner product. Expand the inner product.)
\end{hw}

\begin{hw}
For a graph $G = (V, E)$, and a set of colors $C$, a {\em proper (vertex) coloring} is a
function $s : V \rightarrow C$ such that $s(u) \neq s(v)$ whenever $uv$ is an edge.

Let $G$ be a bipartite graph on $n$ vertices, and let $C$ be a set of $t > \log_2 n$ colors.
For each vertex $v$, suppose we have a list of candidate colors $S(v) \subseteq C$ such that
$|S(v)| > \log_2 n$. Prove that $G$ has a proper coloring $s$ where
$s(v) \in S(v)$ for each vertex $v$.
\end{hw}

\end{document}
