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

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

\begin{document}
\headers{Math773}{Homework 3}{Due Thurs, Feb. 26, 2015}

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

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


\renewcommand{\E}{\mathbb{E}}

\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 {} [MR 2.24] Prove that with high probability, $G_{2k,1/2}$ contains a perfect matching.  (Hint: partition the vertices into sets $A$ and $B$ of size $k$.  Using only randomness in pairs with one vertex in $A$ and the other in $B$, obtain a matching with $2k/3$ edges.  Next, using randomness inside $A$ and inside $B$, modify the existing matching to obtain a perfect matching.)

\item {} \emph{Expected time and distance.}
\begin{enumerate}
	\item Starting in the center of a path on $2r-1$ vertices, a random walk moves in either direction with probability $1/2$ independently of all previous steps.  The walk ends when moving off of either end of the path.  Compute the expected number of steps in the walk.  (Hint: recall that for a path on $k$ vertices, a random walk starting at an endpoint lasts for $k$ steps on average.)
	
	\item Let $X_1, \ldots, X_{2k+1}$ be independent random variables with each $X_i$ chosen uniformly in $\{-1,+1\}$.  Let $X = \sum_i X_i$.  Obtain $\E(|X|)$ in closed form (i.e. not as a sum), and use Stirling's formula to obtain the asymptotic behavior.  Note: this is the expected distance between the starting and ending positions of a random walk on a long path with $2k+1$ steps.  (Hint: a recurrence leads to a non-trivial (but solvable) sum.  For a faster solution, let $Y_i$ be the random variable which is $1$ if $X_i$ and $X$ have the same sign and $-1$ otherwise.)
\end{enumerate}

\item {} Let $S$ be chosen uniformly at random from $\binom{[n]}{k}$ and let $X=\min S$.  Compute $\E(X)$.

\item {} Large chromatic number and clique size.
\begin{enumerate} 
	\item {} [MR 3.6] Show that for $n$ sufficiently large, there exists an $n$-vertex graph with chromatic number at least $n/2$ and $\omega(G) \le O(n^{2/3}\log n)$.
	\item Let $\varepsilon > 0$.  Prove that if $G$ is an $n$-vertex graph and $\chi(G) \ge (\frac{1}{2} + \varepsilon)n$, then $\omega(G)\ge 2\varepsilon n$.
\end{enumerate}

\newcommand{\F}{\mathcal{F}}
\item {} \emph{Sperner's theorem.}  Let $\F$ be a family of subsets of $[n]$, and suppose that $\F$ does not contain distinct sets $A$ and $B$ such that $A\subseteq B$.
\begin{enumerate}
	\item Prove that $\sum_{A\in \F} \frac{1}{\binom{n}{|A|}} \le 1$.  Hint: consider a random ordering of $[n]$.
	\item Conclude from part (a) that $|\F| \le \binom{n}{\floor{n/2}}$.
\end{enumerate}
Comment: since $\binom{[n]}{\floor{n/2}}$ satisfies the given condition, the inequality in (b) is sharp.

\item {} [AS 1.7]  Let $\{(A_1,B_1), \ldots, (A_n,B_n)\}$ be a collection of ordered pairs of sets with $|A_i| = r$ and $|B_i| = s$ for all $i$.  Suppose that $A_i$ and $B_i$ are disjoint for all $i$, but whenever $i\ne j$, at least one of $\{A_i \cap B_j, A_j\cap B_i\}$ is nonempty.  Prove that $n\le \frac{(r+s)^{r+s}}{r^rs^s}$.
\end{enumerate}
\end{document}
