\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math773}{Homework 4}{Due Thurs, Mar. 12, 2015}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}


\renewcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\mathrm{Var}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  All written work must be your own, and you must cite any external sources that you use.

\begin{enumerate}

\item {} [AS 2.9] Let $G$ be a bipartite graph with $n$ vertices let $L$ be a list-assignment with $|L(v)|>\lg n$ for each vertex $v$.  Prove that $G$ has a proper $L$-coloring.

\item {} [AS 3.3] Let $G$ be an $n$-vertex $3$-uniform hypergraph with $m$ edges.  Prove that if $m\ge n/3$, then $\alpha(G) \ge \frac{2n^{2/3}}{3\sqrt{3m}}$.  (In a hypergraph, a set $S$ is an independent set if no edge has all its vertices in $S$.)  

\item {} Let $p=\frac{c\ln n}{n}$ where $c$ is a constant, and let $X$ be the number of isolated vertices in $G_{n,p}$.
\begin{enumerate}
	\item Use the first moment method to show that if $c>1$, then $X=0$ with high probability.
	\item Use the second moment method to show that if $c<1$, then $X\ge 1$ with high probability.
\end{enumerate}
Comment: the function $p(n) = \frac{\ln n}{n}$ is a \emph{threshold} for the disappearance of isolated vertices.  That is, as $G_{n,p}$ evolves from an empty graph ($p=0$) to a complete graph ($p=1$), the isolated vertices disappear at $p=\frac{\ln n}{n}$.

\item {} [AS 4.4]  Let $X$ be a random variable, and let $A$ be an event.  Let $Y$ be the random variable which has value $\E(X|A)$ if $A$ occurs and value $X$ otherwise.
\begin{enumerate}
	\item Prove that $\E(Y) = \E(X)$.
	\item Define the conditional variance $\Var(X|A)$ to be the variance of $X$ in the restriction of $\Omega$ to $A$; that is $\Var(X|A) = \E(X^2|A) - (\E(X|A))^2$.  Prove that $\Var(Y) = \Var(X) - \Var(X|A)\cdot \Pr(A)$.  Conclude that $\Var(Y) \le \Var(X)$.
	\item Use part (b) to show that if $\E(X) = 0$ and $\sigma^2 = \Var(X)$, then $\Pr(X \ge \lambda) \le \frac{\sigma^2}{\sigma^2 + \lambda^2}$ when $\lambda>0$.
\end{enumerate}

\item {} [MR 4.3] Let $G$ be a graph with maximum degree $k$, and let $L$ be a list assignment.  For each vertex $v$, let $w_v$ be a non-negative weight function $w_v\st L(v)\to \R$ such that $\sum_{c\in L(v)} w_v(c) = 1$ for each vertex $v$.  Show that if $\sum_{c\in L(u)\cap L(v)} w_u(c)w_v(c) \le 1/(8k)$ for each edge $uv\in E(G)$, then $G$ has a proper $L$-coloring.

\item {} [CM 14.2.16] Let $G$ be a digraph in which every vertex has outdegree $k$ and indegree $k$, and let $r=\floor{k/(2+2\ln k)}$.  Partition $V(G)$ into $r$ nonempty sets $V_1, \ldots, V_r$ by an appropriate experiment.  Use the Local Lemma to prove that with positive probability every vertex has a successor in the set containing it.  Conclude that every $k$-regular directed graph has a family of $r$-pairwise disjoint cycles.  (Hint: be careful to ensure that $V_1, \ldots, V_r$ are nonempty.)

\end{enumerate}
\end{document}
