\documentclass[11pt]{article} \include{/math/home/fac/saks/COMBNOTES/latexdefs} %\usepackage{amsmath} %\usepackage{amsfonts} %\pagestyle{empty} %This determines whether the page number appears. \topmargin -1.00in \textheight 9in \oddsidemargin 14pt \evensidemargin 14pt \textwidth 440pt \addtolength{\parskip}{0.5\parskip} %\newcommand{\binom}[2]{$\left( \begin{array}{c} %#1 \\ #2 \end{array} \right)$} \newcommand{\nopar}{\hspace{-\parindent}} \newcommand{\fsp}{\hspace{5em}} \newcommand{\tsp}{\hspace{3em}} \newcommand{\osp}{\hspace{1em}} \newcommand{\Rl}{\bf R} \newcommand{\remove}[1]{} \begin{document} \begin{flushleft} {\large MATH 642:582--Fall, 2008} \\ {\bf Assignment 4--Due Monday December 1(Version: November 26)} \\ \end{flushleft} \parskip=10pt A few preliminary remarks. \begin{enumerate} \item Follow the general instructions for homework given in: \begin{center} http://www.math.rutgers.edu/~saks/homework.html \end{center} \item Please be on the look out for errors. If something seems not to make sense, check with me before investing a lot of time on the problem. \end{enumerate} \begin{center} Problems to be handed in. \end{center} \begin{enumerate} \item \label{boxes}A {\em combinatorial box} is the Cartesian product of finite nonempty sets $B=B_1 \times \cdots \times B_n$. For sets $C_1,\ldots, C_n$ with $C_i \subseteq B_i$ we say that $C=C_1 \times \cdots \times C_n$ is a {\em subbox} of $B$; $C$ is a {\em proper subbox} of $B$ if $C_i \neq B_i$ for all $i$. A {subbox partition} of $B$ is a partition of $B$ into subboxes; the partition is {\em proper} if each subbox in the partition is proper. The main purpose of this problem is prove the following Theorem: If $B_1,\ldots,B_n$ all have size at least 2, then any proper subbox partition of $B=B_1 \times \cdots \times B_n$ uses at leasts $2^n$ sets. Warm up problems (not to be handed in) (i) Prove that $B$ has a proper subbox partition into $2^n$ boxes. (ii) Prove the theorem in the case that all $B_i$ have size exactly 2. \begin{enumerate} \item Let $S$ be a finite set and let $T$ be a proper nonempty subset of $S$. Suppose $R$ is selected uniformly at random from among all subsets of $S$ of odd size. Find, with proof, the probability that $|T \cap R|$ is odd? \item Let $B=B_1 \times \cdots \times B_n$ be a box with all $|B_i| \geq 2$ and let $C=C_1 \times \cdots \times C_n$ be a proper subbox. Suppose $R_1,\ldots,R_n$ are selected independently where $R_i$ is selected uniformly at random from among all odd sized subsets of $B_i$. Find, with proof, the probability that $|(R_1 \times \cdots \times R_n) \cap C|$ is odd. \item Prove the theorem. \item Now we consider a generalization of the theorem: For a box $B$ and subbox $C$ (not necessarily proper), define $s(C,B)$ to be the number of $i$ such that $C_i \neq B_i$. Prove that for any subbox partition ${\cal C}$ of $B$, $\sum_{C \in {\cal C}} 2^{-s(C,B)} \geq 1$. \item Now show that the result of the previous part is best possible: Let $s_1,\ldots,s_t$ be any sequence of positive integers satisfying $\sum 2^{-s_i} =1$. Prove that there are sets $B_1,\ldots,B_n$ and a subbox decomposition $C^1,\ldots,C^t$ of $B_1 \times \cdots \times B_n$ such that that $s(C^i,B)=s_i$ for $i \in [t]$. (Hint provided on last page.) \end{enumerate} \item {\bf (20 points)} If $w$ is a weight function on $X$ (mapping $X$ to the nonnegative reals), we extend $w$ to subsets of $X$ by defining $w(Y)=\sum_{y \in Y}w(y)$. Let $\HH$ be a hypergraph on $X$. let $w_{\min}(\HH)$ be the minimum weight of any edge of $\HH$. (This is defined to be infinite for the hypergraph having no edges). We say that $w$ {\em is uniquely minimized over} $\HH$ if there is exactly one edge of weight $w_{\min}(\HH)$. Here is a very nice (and somewhat surprising) fact. \newgroup {\bf Theorem} Let $\HH$ be a hypergraph on $X$ with $|X|=n$. Let $\Omega$ be the set of all weight functions from $X$ to $[2n]$. If $w$ is chosen uniformly at random from $\Omega$, then with probability at least $1/2$, $w$ is uniquely minimized over $\HH$. \newgroup The first two parts of this problem are devoted to the proof of this theorem. The remaining three parts (which can be done independently of the first two parts) apply it to develop a neat randomized algorithm for testing whether a bipartite graph has a perfect matching. \begin{enumerate} \item For a vertex $x$ of $\HH$ the star $\HH$ over $x$,$\starover{\HH}{x}$ is the partial hypergraph with edges set $\{E \in \HH: x \in E\}$. The link of $\HH$ over $x$, $\linkover{\HH}{x}$, is the hypergraph on $X-x$ with edge set $\{E-x:E \in \starover{\HH}{x}\}$, and $\inducedh{\HH}{X-x}$ is the hypergraph on $X-x$ whose edge set is $\{E \in \HH:x \not \in E\}$. Prove that for a hypergraph $\HH$ and a vertex weighting $w$ the following are equivalent: \begin{enumerate} \item $w$ is uniquely minimized over $\HH$. \item For every vertex $x$, $w_{\min}(\inducedh{\HH}{X-x})-w_{\min}(\linkover{\HH}{x}) \neq w(x)$. \end{enumerate} \item Prove the theorem. \item Let $G=\{X,Y;E\}$ be a bipartite graph with $|X|=|Y|=k$. Let ${\cal M}(G)$ be the set of all real valued matrices $M$ indexed by $X \times Y$ that satisfy $M(x,y)=0$ if $(x,y) \not\in E$. Prove that $G$ has a perfect matching if and only if there is a matrix $M \in {\cal M}$ such that $det(M) \neq 0$. \item Let $G$ be as in the previous part. Construct a matrix $M \in {\cal M}(G)$ randomly as follows: for each $(x,y) \in E$, select $j(x,y) \in [2k^2]$ at random and set $M(x,y)=2^{j(x,y)}$. Prove that if $G$ has a perfect matching then the probability that $det(M) = 0$ is less than 1/2. \item Use the results of the previous problems to design a {\em probabilistic test} for whether a bipartite graph has a matching. Such a test should have the following property: given a bipartite graph $G$ and a number $\epsilon>0$ answers ``Yes'' or ``No'' such that: (1) if $G$ has a perfect matching then the test yields ``Yes'' with probability at least $1-\epsilon$ and (2) if $G$ has no perfect matching then the test always says ``No''. \end{enumerate} \item \label{cover} Recall that for hypergraph ${\cal H}$, $\kappa({\cal H})$ is the minimum size of a set of edges covering all of the vertices, and $\kappa^*({\cal H})$ is the minimum weight of a fractional cover by edges (i.e. a nonnegative function defined on edges such that for each vertex, the sum of the weights of edges containing the vertex is at least 1). Prove that there is a constant $c$ such that for every hypergraph ${\cal H}$, $\kappa({\cal H})/\kappa^*({\cal H}) \leq c \log |V({\cal H})|$ (Hint provided on last page.) \item \label{intervals} For $p$ be a prime and let ${\mathbb Z}_p$ denote the integers modulo $p$. An {\em interval} in ${\mathbb Z}_p$ is a set of the form $\{a+1,\ldots,a+r\}$ where $a \in {\mathbb Z_p}$, $r \leq p$ and addition is taken mod $p$. If $X \subseteq {\mathbb Z}_p$ and $a,b \in {\mathbb Z}_p$ we write $aX+b$ for the set $\{(ax+b)\mod p:x \in X\}$. The purpose of this problem is to prove the Theorem: For any subset $X$ of ${\mathbb Z}_p$ there is an $a \in {\mathbb Z}_p$ such that $aX$ has nonempty intersection with every interval of size at least $2p/\sqrt{|X|}$. \begin{enumerate} \item Let $s,t$ be distinct elements of ${\mathbb Z}_p$. Suppose $A,B$ are chosen independently and uniformly from ${\mathbb Z}_p$. Show that $As+B$ and $At+B$ are independent and uniformly distributed over ${\mathbb Z}_p$. \item Let $S,T$ be arbitrary subsets of ${\mathbb Z}_p$, Suppose tha $A,B$ are chosen uniformly at random from ${\mathbb Z}_p$. Prove that $\Pr[(AS+B) \cap T = \emptyset] \leq p/|S||T|$. \item Prove the theorem. \end{enumerate} (Hints are provided on the last page.) \item \label{m_b(n)} {\bf (20 points)} An bipartite graph is said to have order $(s,t)$ if one side has $s$ vertices and the other side has $t$ vertices. $K_{s,t}$ denotes the graph of order $(s,t)$ such that every pair of vertices in different parts are joined by an edge. Here we consider: given integers $n \geq b \geq 1$, what is the maximum $m_b(n)$ number of edges that a bipartite graph of order $(n,n)$ can have and not contain $K_{b,b}$ as a subgraph. (Note that $m_1(n)=0$, but the value of $m_2(n)$ is far from clear.) Assume $b \geq 2$. In this problem you'll prove a lower bound on $m_b(n)$ using the basic probabilistic method, and then improve the bound using the "alteration" method. \begin{enumerate} \item Consider a random $(n,n)$ bipartite graph where each edge is selected independently with probability $p$. Determine the expected number of $K_{b,b}$ subgraphs. \item Show that for $p=n^{-2/b}$ the probability that the graph contains a $K_{b,b}$ subgraph is less than 1/2. %(Note: In analyzing this you may find it convenient %to consider the case %$b=2$ separately.) \item Prove that for each $b$, and for $n$ sufficiently large, $m_b(n) \geq n^{2-2/b}/2$. \item Show that adjusting the probability $p$ in the above argument can not improve the lower bound by more than a constant factor (depending on $b$ but independent of $n$). \item Now let us improve the lower bound by the "alteration" method. Prove that for $p=n^{-2/(b+1)}$ the probability that there are more than $n^2p/2$ $K_{b,b}$-subgraphs is less than 1/2. \item Prove that for some constant $C>0$ (independent of $n$ and $b$), that $m_b(n) \geq C n^{2-2/(b+1)}$. \item Problem withdrawn %\item Use the Lovasz local lemma to obtain a bound %of the form $m_b(n) \geq Cn^{2-\delta(b)}$ %where $\delta(b) < 2/b+1$. In particular, %for $b=2$, you should get a bound of the form $m_2(n)=\Omega(n^{3/2})$. \item For infinitely values of $n$, provide an {\em explicit construction} of an $(n,n)$ bipartite graph $F_n$ with no $K_{2,2}$ having $\Omega(n^{3/2})$ edges $m_2(n) = \Omega(n^{3/2})$. (Hint: Make use of the finite projective plane from Assignment 3, problem 9.) \end{enumerate} \item Recall Ramsey's theorem for graphs says that for every $k$ there is an $n$ such that every graph on at least $n$ vertices has a clique or independent set of size $k$. One of the way's this theorem is generalized is to consider $s$-uniform hypergraphs (for some $s$) instead of graphs. For brevity these are sometimes called $s$-graphs. An independent set in an $s$-graph ${\cal H}$ is a subset $W$ of vertices that contains no edges and a clique is a subset of $W$ that contains all of $\binom{W}{s}$. The graph Ramsey theorem generalizes: For every $s,k$ there is an $n$ such that every $s$-uniform hypergraph on $n$ vertices contains an independent set or clique of size $k$. $R_s(k)$ is defined to be the smallest such $n$. The purpose of this problem is to derive some lower bounds on $R_s(s+1)$. \begin{enumerate} \item Suppose one uses the basic probabilistic method to obtain a lower bound on $R_s(s+1)$. Show that for large $s$ one obtains from this a lower bound of the form: $R_s(s+1) \geq c(s)s$ where $1