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

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

\begin{document}
\headers{Math773}{Homework 6}{Due Thurs, Apr. 23, 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}}
\newcommand{\F}{\mathbb{F}}

\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 {} [CM 15.1.9] Let $A_1, \ldots, A_m$ and $B_1, \ldots, B_m$ be families of subsets of $[n]$ such that $|A_i \cap B_i|$ is odd for all $i$ and $|A_i \cap B_j|$ is even when $i\ne j$.  Prove that $m\le n$.

\item {} [CM 15.1.8] Let $A_1, \ldots, A_m$ be a family of even-sized subsets of $[n]$ such that all pairwise intersections have odd size.
\begin{enumerate}
\item Prove that $m\le n$, with equality possible when $n$ is odd.  Hint: first try to prove that $m\le n+1$ using standard techniques.  Then, add a new polynomial to the independent set that does not increase dimension.
\item Prove that $m\le n-1$ when $n$ is even, with equality possible.  Hint: suppose for a contradiction that $m=n$ and $n$ is even.
\end{enumerate}

\item {} [CM 15.1.23] $3$-Choosability of planar bipartite graphs.
\begin{enumerate}
\item The \emph{maximum density} $\rho(G)$ of a graph $G$ is $\max_{H\subseteq G} |E(H)|/|V(H)|$.  Prove that if $\rho(G) \le d$, then $G$ has an orientation with outdegree at most $d$.
\item Conclude from part (a) that planar bipartite graphs are $3$-choosable.
\end{enumerate}

\item {} [CM 15.1.29] Use the Combinatorial Nullstellensatz to prove that the minimum number of hyperplanes in $\mathbb{R}^n$ that do not contain $0$ but together cover all the other points in $\{0,1\}^n$ is $n$.  (Recall that a hyperplane in $\R^n$ is a set of points of the form $\{x\in \R^n \st  \left< x,v\right> = c\}$ for some $c\in \R$ and a non-zero $v\in\R^n$.) 

\item {} [CM 15.2.23] The Permanent Lemma.
\begin{enumerate}
\item Let $A$ be an $n$-by-$n$ matrix with nonzero permanent over a field $\F$.  Use the Combinatorial Nullstellensatz to prove that for any $b\in\F^n$ and sets $S_1, \ldots, S_n$ of size $2$ in $\F$, there is a vector $x\in \prod_{i=1}^n S_i$ such that $Ax$ differs from $b$ in every coordinate.
\item Let $p$ be a prime.  Prove that every list of $2p-1$ members of $\Z_p$ contains $p$ entries that sum to $0$ modulo $p$.
\end{enumerate}

\item {} [CM 15.3.16] Let $B_1, \ldots, B_m$ be a bliclique decomposition of the clique with vertex set $[n]$, with $B_k$ having partite sets $X_k$, $Y_k$.  Let $A_k$ be the $0,1$-matrix having $1$ in position $(i,j)$ if and only if $i\in X_k$ and $j\in Y_k$.  Let $S=\sum_{k=1}^m A_k$.

Observe that $S+S^T = J-I$.  Prove that every $n$-by-$n$-matrix satisfying this equation has rank at least $n-1$.  Since $\rank(A+A')\le \rank(A)+\rank(A')$ for all matrices $A$ and $A'$, conclude $\rank S\le m$ and therefore $m\ge n-1$.

Hint: to show $\rank S\ge n-1$, assume for a contradiction that $\rank S \le n-2$, add observe that adding any additional row gives an $(n+1)$-by-$n$ matrix $S'$ with rank less than $n$, so that $S'x=0$ has a nontrivial solution.

\end{enumerate}
\end{document}
