\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[all]{xy}

\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\degree}{\operatorname{degree}}
\newcommand{\divides}{\mbox{ \Large{$\vert$} }}

\parindent=0cm

\oddsidemargin=0in
\textwidth=6.5in

\newenvironment{question}[1]{\noindent{\large{\bf{Problem #1}}}\hspace{1em} \begin{em}}{\end{em}\bigskip}
\newenvironment{solution}{\noindent\ignorespaces\par\noindent \large{\bf{Solution}} }{\bigskip}

\title{The Probabilistic Method\\Homework 1}
\author{Brett Hemenway}

\begin{document}
	\maketitle
	
	\begin{question}{1}
		Suppose $n \ge 4$ and let $H$ be an $n$-uniform hypergraph with at most $\frac{4^{n-1}}{3^n}$ edges.
		Prove that there is a coloring of the vertices of $H$ by 4 colors so that in every edge all $4$ colors are represented.
	\end{question}

	\begin{solution}
		Suppose we color each vertex randomly, i.e. with probability $1/4$ it gets one of each of four colors.  Let us calculate the probability
		that for a given edge it does not receive all four colors.  There are at less than $4 \cdot 3^n$ (this number double counts colorings using only two colors) 
		distinct colorings using only three colors and $4^n$ distinct colorings, thus the probability that an edge does \emph{not} receive the four distinct colors is $\frac{4 \cdot 3^n}{4^n}$.

		If $H$ has $k$ edges, then the union bound gives that the probability that at least one edge does not receive all four colors is less than 
		or equal to $k \cdot \frac{4 \cdot 3^n}{4^n}$, if $k < \frac{4^{n-1}}{3^n}$, this probability is strictly less than one, so in particular there 
		exists a coloring in which every edge receives all four colors.
	\end{solution}

	\begin{question}{2}
		Let $\F$ be a family of subsets of $N = \{1,2,\ldots,n\}$ and suppose there are no $A,B \in \F$ satisfying $A \subset B$.
		Prove that $|\F| \le \binom{n}{\lfloor n/2 \rfloor}$.\\

		\bf{Hint.}  Consider a random permutation of the elements of $N$.
	\end{question}

	\begin{solution}
		This solution is not probabilistic, but it is short, so I hope it is not too big a violation of your principles.

		Consider all chains of strictly increasing subsets of $\{1,\ldots,n\}$ of length $n$.  If $A_1 \subsetneq A_2 \subsetneq \cdots \subsetneq A_n$ is such a chain then 
		$|A_1| = 1$, $|A_2| = 2$, $\ldots |A_n| = n$.  Since there are $n$ choices for $A_1$, $n-1$ choices for $A_2$ etc, there are $n!$ such chains.
		By the definition of $\F$, each element of $\F$ is in exactly one such chain.  Now, if $A$ is a subset of size $k$, it is in $k!(n-k)!$ chains,
		since there are $k!$ choices for the subsets contained in $A$, and $(n-k)!$ choices for the subsets containing $A$.  If we let $a_k$ denote the number of subsets of $\F$ of size $k$.
		Then we have the inequality
		\[
			\sum_{k=1}^n a_k k!(n-k)! \le n!.
		\]
		Since the number on the left is the total number of chains containing elements of $\F$, and the number on the right is the total number of  chains.  Dividing both sides by $n!$, we have
		\[
			\sum_{k=1}^n \frac{a_k}{\binom{n}{k}} \le 1.
		\]
		Since $\binom{n}{k}$ is maximized when $k = \lfloor n/2 \rfloor$, we have 
		\[
			\sum_{k=1}^n \frac{a_k}{\binom{n}{\lfloor \frac{n}{2} \rfloor}} \le 1.
		\]
		Thus
		\[
			|\F| = \sum_{k=1}^n a_k \le \binom{n}{\lfloor \frac{n}{2} \rfloor}.
		\]

		Note that by letting $\F$ be the collection of all subsets of $\{1,\ldots,n\}$ of size $\lfloor n/2 \rfloor$ we actually achieve this bound.

		To obtain this result using probabilistic methods, consider a random $\sigma \in S_n$, now suppose $I \in \F$ with $|A| = k$.  Then 
		\[
			\Pr ( A = \{\sigma(1),\ldots,\sigma(k)\} ) = \frac{k!(n-k)!}{n!} = \frac{1}{\binom{n}{k}} = \frac{1}{\binom{n}{|A|}}.
		\]
		By the property of $F$, these events are disjoint for all $A,B \in \F$, thus we have 
		\[
			\sum_{A \in \F} \frac{1}{\binom{n}{|A|}} \le 1.
		\]
		Thus
		\[
			\frac{|\F|}{\binom{n}{\lfloor n/2 \rfloor}} = \sum_{A \in \F} \frac{1}{\binom{n}{\lfloor n/2 \rfloor}} \le \sum_{A \in \F} \frac{1}{\binom{n}{|A|}} \le 1.
		\]

	\end{solution}

	\begin{question}{3}
		Let $G = (V,E)$ be a graph on $n \ge 10$ vertices and suppose that if we add to $G$ any edge not in $G$ then the number 
		of copies of a complete graph of $10$ vertices in it increases.  Show that the number of edges of $G$ is at least $8n-36$.
	\end{question}

	\begin{solution}
		For convenience, call the property above property $A$.  First notice that for any graph with property $A$ every vertex $v$ must have at least $8$ 
		neighbors since adding an edge between $v$ and any other vertex results in a new complete graph on $10$ vertices, thus $v$ must now be connected to at least $9$
		other vertices.  Note that this immediately gives the lower bound $|E| \ge 4n$.

		Now, we proceed by induction.  Suppose $G$ is a graph with property $A$, and $n = 10$, since $\binom{10}{2} = 45$, and after we add an edge to $G$ we have at least one complete graph on 
		$10$ vertices, $G$ must have begun with at least $44$ edges, but $44 = 8*10 - 36$.  Assume any graph with property $A$ and $|V| \le n$ must have $|E| \ge 8n - 36$.  Now let $G$ 
		be a graph with property $A$ and $|V| = n+1$.  Now, pick any two vertices in $G$ which are not neighbors.  Since joining them creates a new copy of $K_{10}$, they must have at least $8$ common neighbors.
		Now, replace these two vertices by a single vertex, connecting it to all vertices that were neighbors of either of the two removed vertices.  Since the two vertices have at least $8$ common neighbors, 
		the number of edges decreases by at least $8$ and the number of vertices decreases by $1$.  Now, it's not hard to see that the resulting graph also has property $A$.
		
	\end{solution}

	\begin{question}{4}
		Let $G = (V,E)$ be a bipartite graph on $n$ vertices with a list $S(v)$ of at least $\log_2 n$ colors associated with each 
		vertex $v \in V$.  Prove that there is a proper coloring of $G$ assigning to each vertex of $v$ a color from its list $S(v)$.
	\end{question}

	\begin{solution}
		Since $G$ is bipartite, its vertices can be split into two sets $A$ and $B$ such that all edges go from a vertex in $A$ to a vertex in $B$.
		Thus if we can two disjoint sets of colors $S_A$ and $S_B$, and color the vertices from set $A$ with the colors $S_A$ and the vertices in $B$ with $S_B$,
		this will be a proper coloring.  Let $S = \bigcup_{v \in V} S(v)$ be the complete list of all colors.  Now, consider creating the sets $S_A$ and $S_B$ at 
		random by choosing a color in $S$ and with probability $1/2$ putting it in $S_A$ and probability $1/2$ putting it in $S_B$.  Now, consider a vertex in $v \in A$.
		The probability that there is a no color on its list in $S_A$ is $\frac{1}{2^{|S(v)|}}$ since each color in $S(v)$ is in $S_A$ with probability $1/2$ and they are all independent.
		Since $|S(V)| > \log_2 n$, the probability that $v$ cannot be colored by some color in $S_A$ less than $\frac{1}{n}$.  Clearly the same argument holds for vertices in $B$.
		Since there are $n$ vertices and the probability that any one vertex cannot be colored by an element in its list is less than $1/n$, the union bound gives that the probability that at 
		least one of the vertices cannot be colored by an element in its list is strictly less than one.  Thus we conclude that there exists a proper coloring where each vertex is colored by an color
		from its list.
	\end{solution}

	\begin{question}{5}
		Prove that there is an absolute constant $c > 0$ with the following property.  Let $A$ be an $n \times n$ matrix with pairwise distinct entries.
		Then there is a permutation of the rows of $A$ so that no column in the permuted matrix contains an increasing subsequence of length at least $c \sqrt{n}$.
	\end{question}

	\begin{solution}
		Pick a random permutation of the columns.  Let us calculate the probability that the first column has an increasing subsequence of length $c\sqrt{n}$.  There are $\binom{n}{c\sqrt{n}}$ such subsequences, 
		and each one has a probability of $\frac{1}{(c\sqrt{n})!}$ of being in increasing order.  Thus the probability that any of the $n$ columns contains a subsequence of length $c \sqrt{n}$ in increasing order is 
		\[	
			p = n \binom{n}{c\sqrt{n}} \frac{1}{(c\sqrt{n})!}.
		\]
		Thus, we just need to choose $c$ such that $p < 1$.  Now use the estimates $\binom{n}{k} \le \left( \frac{en}{k} \right)^k$ and $k! \ge \left(\frac{k}{e}\right)^k$.
	\end{solution}

\end{document}