\documentclass[11pt]{article} \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 2--Due October 16 (Version: October 4)} \\ \end{flushleft} \parskip=10pt A few preliminary remarks. \begin{enumerate} \item Follow the general instructions for homework given in: \begin{quote} http://www.math.rutgers.edu/~saks/homework.html \end{quote} \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. \item "A Course in Combinatorics" Chapters 5 and 6 by van Lint and Wilson provides a general reference for the K\"onig-Hall theorem and Dilworth's theorem \item This homework uses the following definitions: \begin{itemize} \item If $V$ is a set, a {\em hypergraph} ${\cal H}$ on $V$ is a set of nonempty subsets of $V$. The members of ${\cal H}$ are called {\em edges} and $V$ is called the {\em vertex set}. \item If ${\cal H}$ is a hypergraph on $V$, then ${\cal H}^{\downarrow}$ is the hypergraph $\{W \subseteq V: \exists E \in {\cal H}, W \subseteq E\}$ and ${\cal H}^{\uparrow}$ is the hypergraph $\{W \subseteq V: \exists E \in {\cal H}, E \subseteq W\}$ \item A {\em matching} of ${\cal H}$ is a subset of edges that are pairwise disjoint. The {\em matching number} $\nu({\cal H})$ is the size of the largest matching of ${\cal H}$. \item A {\em fractional matching} is a nonnegative real-valued function $w$ with domain ${\cal H}$ satisfying that for every vertex $v$, $\sum_{E:v \in E}w(E) \leq 1$. The {\em fractional matching number $\nu^*({\cal H})$} is the maximum of $\sum_{E \in {\cal H}} w(E)$ over all fractional matchings of ${\cal H}$. \item A {\em vertex cover} (or {\em blocking set} of ${\cal H}$ is a subset $C$ of vertices such that $C \cap E \neq \emptyset$ for all $E \in {\cal H}$. $\tau({\cal H})$ is the minimum size of a vertex cover. \item A {\em fractional vertex cover} of ${\cal H}$ is a nonnegative real valued function $\kappa$ defined on $V$ with the property that for every edge $E$, $\sum_{v \in E} w(v) \geq 1$. The {\em fractional cover number} $\tau^*({\cal H})$ is the minimum of $\sum_v w(v)$ over all fractional vertex covers. \item The incidence matrix $M=M({\cal H})$ of ${\cal H}$ is the matrix with rows indexed by edges and columns indexed by vertices, where $M_{E,v}=1$ if $v \in E$ and is 0 otherwise. \item A hypergraph is {\em intersecting} if $E \cap F \neq \emptyset$ for all $E,F \in {\cal H}$ and is {\em $k$-wise intersecting} if $E_1 \cap \cdots \cap E_k \neq \emptyset$ for all $E_1,\ldots,E_k \in {\cal H}$. \item For a graph $G=(V,E)$, a {\em clique} is a subset of vertices that are pairwise adjacent, and an {\em independent set} is a subset of vertices that are pairwise non-adjacent. \end{itemize} \end{enumerate} \begin{enumerate} \item \begin{enumerate} \item For a hypergraph ${\cal H}$ be a hypergraph on $V$, let ${\cal H}^C$ denote the hypergraph consisting of all vertex covers of ${\cal H}$. Prove that $({\cal H}^{C})^C={\cal H}^{\uparrow}$. \item For a hypergraph ${\cal H}$,let ${\cal H}^A=\{W \subseteq V: \forall S \in {\cal H}, |W\cap S| \leq 1\}$. Let $G({\cal H})$ be the graph on $V$ whose edge set is the set $\{uv: \exists S \in {\cal H}, \{u,v\} \subseteq S\}$. Prove that ${\cal H}^A$ is equal to the hypergraph consisting of all independent sets of $G({\cal H})$ and $({\cal H}^{A})^{A}$ is equal to the hypergraph of all cliques of $G({\cal H})$. \end{enumerate} \item \label{critical} A hypergraph ${\cal H}$ is {\em $\tau$-critical} if for any edge $E$ of ${\cal H}$, $\tau({\cal H}-\{E\})<\tau({\cal H})$. Let ${\cal H}$ be a $\tau$-critical hypergraph. Prove that either the edges of ${\cal H}$ are pairwise disjoint or $\tau^*({\cal H}) < \tau({\cal H})$. \item Let ${\cal H}$ be a hypergraph on $V$ and $M=M({\cal H})$ be its incidence matrix (defined above). \begin{enumerate} \item Prove that if every square submatrix of $M$ has determinant in $\{0,1,-1\}$ then $\nu({\cal H})=\tau({\cal H})$. \item Prove that if ${\cal H}$ is a bipartite graph (so $V$ can be partitioned into two sets $V_1,V_2$ and every edge contains one vertex from $V_1$ and one from $V_2$) then every square submatrix of $M$ has determinant in $\{0,1,-1\}$. \end{enumerate} \item Dilworth's theorem says: for any partially ordered set $P$, the width of $P$ (maximum size of an antichain) is equal to the minimum size of a cover of $P$ by chains. For a finite set $\Gamma$, let $A[\Gamma]=\{A_{\alpha}:\alpha \in \Gamma\}$ an indexed collection of sets. For $J \subseteq \Gamma$ we write $A[J]$ for the subcollection $\{A_{\alpha}:\alpha \in J\}$. The defect of $A[J]$ is defined to be $\max\{0,|J|-|\cup_{\alpha \in J}A_{\alpha}|\}$. A selection function for ${\cal A}$ is a map $f$ defined on $\Gamma$ such that $f(\alpha) \in A_{\alpha}$. The {\em defect} of a selection function $f$ is equal to $|\Gamma|-|Range(f)|$. The (defect form of) the K\"onig-Hall Marriage theorem says: for any finite indexed collection of sets $A[\Gamma]$, the minimum defect of a selection function is equal to the maximum deficiency of a subcollection. (Not to hand in: Show the equivalence between this theorem and K\"onig's theorem that $\nu(G)=\tau(G)$ for any bipartite graph $G$.) \begin{enumerate} \item Deduce the K\"onig-Hall Theorem from Dilworth's theorem. \item Deduce Dilworth's theorem from the K\"onig-Hall Theorem. \end{enumerate} \item \begin{enumerate} \item Suppose that $r\leq n$ and $M$ is an $r \times n$ matrix satisfying: \begin{description} \item[(i)] all entries are in $[n]$. \item[(ii)] within any row or column the entries are distinct. \end{description} Prove that there is an $n \times n$ matrix $M'$ satisfying (i) and (ii) such that $M$ is a submatrix of $M'$. \item More generally, for $r,s \leq n$ show that if $M$ is an $r \times s$ matrix satisfying (i) and (ii) then there exists an $n \times n$ $M'$ satisfying (i) and (ii) such that $M$ is a submatrix of $M'$ if and only if if each integer between 1 and n appears at least $r+s-n$ times in $M$. \end{enumerate} \item Let $A[\Gamma]$ be an finite indexed family of subsets of the set $X$. A ${\Gamma} \times X$ matrix $M$ is {\em compatible} with $A[\Gamma]$ if for all $x \in X$ and $\alpha \in \Gamma$, if $x \not \in A[\alpha]$ then $M[\alpha,x]=0$. \begin{enumerate} \item Prove that $A[\Gamma]$ has an injective selection function if and only if there is a nonnegative matrix compatible with $A[\Gamma]$ whose row sums are each at least 1, and whose column sums are each at most 1. \item Let $A[\Gamma]$ be an finite indexed family of subsets of $X$. For $x \in X$, let $deg(x)=|\{\alpha:x \in A_{\alpha}\}|$. Prove: if for every $\alpha \in \Gamma$ and $x \in A_{\alpha}$ $|A_{\alpha}| \geq deg(x)$, then $A[\Gamma]$ has an injective selection function. \end{enumerate} \item \label{r+1 wise} \begin{enumerate} \item Prove: if ${\cal H}$ is an $r$-uniform $r+1$-wise intersecting hypergraph, then $\tau({\cal H})=1$. \item More generally, prove:if ${\cal H}$ is an $r$-uniform $k$-wise intersecting then $\tau(H)\leq \frac{r-1}{k-1}+1$. (A hint appears at bottom of assignment.) \item For each $r,k \in {\bf N}$ such that $k-1$ divides $r-1$, give an example of an $r$-uniform $k$-intersecting hypergraph ${\cal H}(k,r)$ such that $\tau({\cal H})=\frac{r-1}{k-1}+1$. \end{enumerate} \item \label{downset-upset} % For a partially ordered set $P$ and $X \subseteq P$, %$X^{\downarrow}$ denotes the set $\{y \in P: \exists x \in P, y \leq x \}$. %$X^{\uparrow}$ denotes the set $\{y \in P: \exists x \in P, y \geq x \}$. Consider $2^{[n]}$ with the usual containment order. Let ${\cal A}$ be a maximal antichain of $2^{[n]}$. Prove that ${\cal A}$ can be partitioned into two sets ${\cal X}$ and ${\cal Y}$ such that $({\cal X}^{\downarrow}$, ${\cal Y}^{\uparrow})$ is a partition of $2^{[n]}$. (A hint appears at bottom of assignment.) \item The purpose of this problem is to prove a generalization of the Marriage theorem (which, in particular, gives a different proof of Hall's theorem). For an indexed family $A[\Gamma]$ of sets, the surplus is $|\cup_{\alpha \in \Gamma} A_{\alpha}|-|\Gamma|$. The global surplus of $A[\Gamma]$ is defined to be the minimum surplus of any indexed subfamily $A[\Gamma']$ where $\Gamma' \subseteq \Gamma$. If $A(\Gamma)$ and $B(\Gamma)$ are indexed families of sets (with the same index set $\Gamma$) we say that $B$ is a {\em pruning} of $A$ if $B_{\alpha} \subseteq A_{\alpha}$ for all $\alpha \in \Gamma$. \vspace{.1 in} \noindent {\bf Theorem.} Suppose $A[\Gamma]$ has global surplus $s \geq 0$. Then $A[\Gamma]$ has a pruning $B[\Gamma]$ with global surplus $s$ and all of its sets of size exactly $s+1$. \vspace{.2 in} \noindent (Not to hand in: (i) Why is this a generalization of Hall's theorem? (ii) In the case that $s=1$ the conclusion is equivalent to: $A[\Gamma]$ can be pruned to a graph (all edges of size 2) that has no cycles,i.e., is a forest.) \begin{enumerate} \item If $\Gamma' \subseteq \Gamma$ is nonempty and the surplus of $A[\Gamma']$ is equal to the global surplus of $A[\Gamma]$, we say that $\Gamma'$ is {\em surplus critical} for $A[\Gamma]$. Prove that if $\Gamma_1$ and $\Gamma_2$ are surplus critical for $A[\Gamma]$ then $\Gamma_1 \cap \Gamma_2$ is either empty or is also surplus critical for $A[\Gamma]$. \item $\alpha \in \Gamma$ is {\em unshrinkable} for $A[\Gamma]$ if replacing $A_{\alpha}$ by any a proper subset reduces the global surplus of ${\cal H}$. Prove that if $\alpha$ is unshrinkable for $A[\Gamma]$ then then there is a surplus critical set $\Gamma'$ that contains $\alpha$, such that $A_{\beta} \cap A_{\alpha}=\emptyset$ for all $\beta \in \Gamma'$ with $\beta \neq \alpha$. \item Prove the theorem. \end{enumerate} \end{enumerate} Hints: \begin{description} \item[Number \ref{r+1 wise}] For problem \ref{r+1 wise}, part b. Prove by induction on $j$ the claim that for $j \leq k$, there is a set of $j$ edges whose intersection has size at most $r-(\tau({\cal H})-1)(j-1)$. \item[Number \ref{downset-upset}] Let ${\cal X}$ be a minimal subset of ${\cal A}$ satisfying ${\cal A}^{\downarrow}-{\cal A} \subseteq {\cal X}^{\downarrow}.$ \end{description} \end{document}