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

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

\begin{document}
\headers{Math773}{Homework 1}{Due Fri, Jan. 29, 2015}

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

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


\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.4] Airlines find that each passenger who reserves a seat fails to turn up with probability $0.1$ independently of the other passengers.  So an airline sells 10 tickets for a 9 seat airplane and 20 tickets for an 18 seat airplane.  Which type of plane is more frequently overbooked?

\kgmcomment{
\item {} Let $X$ and $Y$ be chosen independently from $\{1,\ldots,n\}$ according to the same distribution.  (The distribution is not necessarily uniform.)  Prove that $\Pr(X=Y) \ge 1/n$. 
}

\item {} Let $\varepsilon$ be a positive constant.  Let $X$ be the length of a longest run of heads in a sequence of $m$ flips of a fair coin.
\begin{enumerate}
	\item Prove that with high probability, $X \le (1+\varepsilon)\lg m$.
	\item Prove that with high probability, $X \ge (1-\varepsilon)\lg m$.
\end{enumerate}
Comment: it can be shown that when $c$ is a fixed integer, $\Pr(X=(\lg m) - 1 + c)$ approaches $e^{-2^{-(c+1)}} - e^{-2^{-c}}$ as $m$ increases over powers of 2.  The probability that $X$ is exactly $(\lg m) - 1$ (the most likely value) approaches $e^{-1/2} - e^{-1} \approx 0.239$.  The probability that $(\lg m) - 2 \le X \le \lg m$ tends to approximately $0.643$.  This is somewhat surprising.  If you flip a coin $2^{20}$ times (over 1 million flips), the length of a longest run of heads will be either 18, 19, or 20 more than 64\% time. 

\item {} Let $x_1, \ldots, x_k$ be a list of integers, each of which is independently selected uniformly at random from $\{1,\ldots,n\}$.
\begin{enumerate}
	\item Show that the probability that no repetitions occur is at most $e^{-\frac{1}{n}\binom{k}{2}}$.
	\item Use part (a) to show that if $1+\sqrt{n \ln n}$ objects are randomly selected with replacement from a set of size $n$, then with high probability some object is selected at least twice.
\end{enumerate}

\item {} Recall that a \emph{tournament} is an orientation of a complete graph.  A \emph{Hamiltonian path} is a path containing each vertex.  Prove that for each $n$, there exists an $n$-vertex tournament with at least $n!/2^{n-1}$ Hamiltonian paths.  For example, with $n=3$, the directed $3$-cycle has $3$ Hamiltonian paths (one starting from each vertex).

\item {} Bipartite subgraphs.
\begin{enumerate}
	\item Use the first moment method to show that every graph with $m$ edges contains a bipartite subgraph with at least $m/2$ edges.
	\item Modify your argument in part (a) to show that if $G$ has $m$ edges and a matching of size $k$, then $G$ contains a bipartite subgraph with $(m+k)/2$ edges.
\end{enumerate}

\item {} \emph{A deterministic construction.}  Let $G_k$ be the graph whose vertices are the triples $(x_1,x_2,x_3)$ such that $1\le x_i \le k$ for each $i$ with edges joining pairs that differ in exactly two coordinates.  For example, in $G_5$ there is an edge joining $(3,4,5)$ and $(3,5,2)$, but $(3,4,5)$ and $(3,2,5)$ are nonadjacent.
\begin{enumerate}
	\item Draw $G_2$, and use your drawing to describe $G_2$ in terms of familiar graphs.
	\item By symmetry, all vertices in $G_k$ have the same degree; that is, $G_k$ is a \emph{regular} graph.  Find the degree of regularity.
	\item Prove that $\omega(G_k) \le 3k-2$.  (Note: this can be improved to $\omega(G_k) \le \max\{4,k\}$ without much additional work.)
	\item Prove that $\alpha(G_k) \le 3k$.  Hint: if $S$ is an independent set in $G_k$, form auxiliary graph $H$ with vertex set $S$ where $x$ and $y$ are adjacent if $x$ and $y$ differ in exactly one coordinate.  For each edge $xy\in E(H)$, color $xy$ with the coordinate in which $x$ and $y$ differ.  So, $H$ is a graph in which every edge receives one of three possible colors.  What can you say about the structure of $H$?
	\item Conclude that if $n$ is a perfect cube, then there exists an $n$-vertex graph $G$ with $\max\{\alpha(G), \omega(G)\} \le 3n^{1/3}$
\end{enumerate}

\end{enumerate}
\end{document}
