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

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

\begin{document}
\headers{Math773}{Homework 2}{Due Thurs, Feb. 12, 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 {} 
\begin{enumerate}
	\item Recall that $\alpha(G) \ge \sum_{v\in V(G)} \frac{1}{d(v)+1}$.  Use this to show that if $G$ is an $n$-vertex graph with $m$ edges, then $\alpha(G) \ge \frac{n^2}{2m+n}$.
	\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$. 
\end{enumerate}

\item {} The outdegree of a vertex $v$ in a directed graph is denoted by $d^+(v)$.
\begin{enumerate}
	\item Give a short probabilistic proof that for each $n$, there exists an $n$-vertex tournament with at least $\frac{1}{4}\binom{n}{3}$ directed triangles.
	\item Prove that the number of directed triangles in an $n$-vertex tournament $T$ is exactly $\binom{n}{3} - \sum_{v\in V(T)} \binom{d^+(v)}{2}$.
	\item Prove that every $n$-vertex tournament has at most $\frac{1}{4} \binom{n+1}{3}$ directed triangles.
\end{enumerate}

\item {}[AS 1.4] Let $G$ be a graph with $n$ vertices and minimum degree $k$.  Prove that there is a partition of $V(G)$ into two parts $A$ and $B$ such that $|A| \le O\left(\frac{\log k}{k} n\right)$ and every vertex in $B$ has at least one neighbor in $A$ and at least one neighbor in $B$.

\item {} Let $S$ be a collection of binary strings, and let $n_k$ be the number of strings in $S$ of length $k$.
\begin{enumerate}
	\item Suppose that no string in $S$ is a prefix of another string in $S$.  Prove that $\sum_{k\ge 0} \frac{n_k}{2^k} \le 1$.
	\item {}[Bonus] Suppose that every binary string is obtained as the concatenation of strings in $S$ in at most one way.  (For example, we allow $S = \{0, 01\}$ but $S$ cannot contain $0$, $10$, and $01$ since $010 = 0(10)$ and $010 = (01)0$.)  Prove that $\sum_{k\ge 0} \frac{n_k}{2^k} \le 1$.
\end{enumerate}

\item {}[CM] Let $G$ be an $n$-vertex graph and let $s$ be an integer with $1\le s\le n$.  Consider an experiment which an $s$-subset $S$ of $V(G)$ is chosen uniformly at random.  The subgraph of $G$ induced by $S$ is denoted $G[S]$.
\begin{enumerate}
	\item Compute the expected number of components of $G[S]$ when $G$ is a cycle and when $G$ is a tree.
	\item Compute the expected number of components of $G[S]$ having size $k$ when $G$ is a cycle and when $G$ is a path.
\end{enumerate}

\item {} A tournament $G$ is $k$-egalitarian if, for each set of vertices $S$ with $|S| \le k$, there exists a vertex $u$ such that $S\subseteq N^+(u)$.  (Recall that $N^+(u)$ denotes the outneighborhood of $u$.)
\begin{enumerate}
	\item Prove that if $\binom{n}{k}(1-2^{-k})^{n-k} < 1$, then there exists an $n$-vertex tournament that does not contain a dominating set of size $k$.
	\item Let $f(k)$ be the minimum number of vertices in a $k$-egalitarian tournament.  Conclude from (a) that $f(k) \le (1+o(1))(\ln 2)k^2 2^k$.
\end{enumerate}
\end{enumerate}
\end{document}
