\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 3--Due November 7 (Version: November 3)} \\
\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.
\item This homework uses the following definitions.  Let $P$
be a partially ordered set.
\begin{itemize}
\item 
The comparability graph of $P$ is the undirected graph
with vertex set $P$ and $xy$ an edge if and only if
$x<y$ or $y<x$.  We say that {\em  $P$ is connected} if and only
if its comparability graph is connected.
\item For $x,y \in P$, the {\em interval}
$[x,y]$ is the set of elements $\{z \in P:x \leq z \leq y\}$.
In particular $[x,y]$ is empty if $x$ is not less than or equal to $y$.
We say that {\em $y$ covers $x$} if $[x,y]=\{x,y\}$.
\item
The cover digraph of $P$ (also called the Hasse diagram)
is the directed graph with arc set $\{(y,x): y \text{ covers } x\}$.
\item
A rank function for $P$ is a function $r$ from $P$ to $\mathbb{Z}$
with the property that whenever $y$ covers $x$,
$r(y)=r(x)+1$.  We call the pair $(P,r)$
a {\em ranked poset} or {\em graded poset}.    
If $P$ has a rank function we often say
{\em $P$ is a ranked poset}, leaving
the rank function implicit.  
\item
If $r$ is a rank function of $P$, and $j \in \mathbb{Z}$
the {\em $j$th level of $P$} with respect to $r$ is
$r^{-1}(i)$.
\item If $(P,r)$ is a finite ranked poset then the
sequence $(w_i:i \in \mathbb{Z})$ where
$w_i=w_i(P,r)=|r^{-1}(i)|$ 
is called the rank sequence of $(P,r)$ (or sometimes
the {\em Whitney numbers of the second kind.})
\item If we say $P$ is a ranked poset with level
sequence $P_s,P_{s+1},\ldots,P_t$ we mean that the rank function associated
to $P$ is the function sending
$P_i$ to $i$.
\item A ranked poset $(P,r)$ is said to be {\em rank unimodal}
if its rank sequence $(w_i:\in \mathbb{Z})$ is unimodal,
that is for some $s$ we have $w_{i-1} \leq w_i$ for $i\leq s$
and $w_{i-1} \geq w_i$ for $i>s$. 
$(P,r)$ is {\em rank symmetric} if for some
$k$ we have $w_i=w_{k-i}$ for all $i$.
\item
$P$ satisfies the Jordan-Dedekind chain condition (JDC)
if for any pair of elements $x \leq y$, every maximal
chain from $x$ to $y$ has the same size.
\item If $P$ is a ranked poset with level sets $P_0,\ldots,P_k$
a chain $C$ of $P$ is a {\em rank symmetric chain} if
for some $i \leq k/2$, $P$ contains one element
from each of the levels $P_i,P_{i+1},\ldots,P_{k-(i+1)},P_{k-i}$.
A {\em symmetric chain decomposition}
of $P$ is a partition of $P$ into symmetric chains.
$P$ is a {\em symmetric chain order} if it has a symmetric chain
decomposition.
\item For a poset $P$, a Sperner $k$-family is a
subset of elements that contains no chain of size $k+1$;
equivalently it is a subset that can be covered by $k$ antichains.
$a_k(P)$ denotes the size of the largest Sperner $k$-family.
\item For a ranked poset $P$ with level sequence $P_0,\ldots,P_s$,
we say that $P$ has the {\em Sperner property} if $a_1(P)=\max_i |P_i|$, 
and has the {\em $k$-Sperner property} if $a_k(P)$ is equal to the
maximum of $|P_{i_1}|+\cdots+|P_{i_k}|$ over all 
sequences $0 \leq i_1 < i_2 < \cdots < i_k \leq s$.
$P$ has the {\em Strong Sperner property} if it is $k$-Sperner for all $k$.
\item The product of posets $P,Q$, $P \times Q$
is the poset with elements $(x,y)$ with $x \in P$ and $y \in Q$
and order $(x,y) \leq (x',y')$ if $x \leq x'$ and $y \leq y'$.
\end{itemize}
\end{enumerate}


\begin{center}
Some warm-up exercises NOT TO BE HANDED IN. You may
refer to these results in solving later problems)  
\end{center}
\begin{enumerate}
\item
If $P$ is finite, prove that
$x<y$ if and only if there is a directed path from
$x$ to $y$ in the cover graph.  
\item Show that the previous result need not
hold if $P$ is infinite.
\item 
Prove that if $P$ is a finite ranked connected poset 
then for each integer $a$, there is a unique rank function
satisfying $a=\min_{x \in P}r(x)$. (Also show that this
is not true if $P$ is disconnected.)
\item 
Prove that if $P$ is finite and has the property that every
maximal chain has the same size, then $P$
satisfies the JDC condition.
\item Prove that if $P$ is finite and satisfies the Jordan Dedekind
chain condition then $P$ is ranked.
\item If $(P,r)$ and $(Q,s)$ are ranked posets then the function
$t$ on $P \times Q$ given by $t(x,y)=r(x)+s(y)$ is a rank
function on $P \times  Q$.
\end{enumerate}

\begin{center}
Problems to be handed in.
\end{center}

\begin{enumerate}

\item
\label{LYM}
In the following, $P$ denotes a ranked poset with rank function $r$ and
nonempty level sets $P_0,\ldots,P_k$.


\begin{itemize}
\item
A bipartite graph $G=(V,W;E)$ is said to have the {\em normalized
matching property} if for all $X \subseteq V$, $|N(X)|/|W| \geq |X|/|V|$.
$P$ is said to have the {\em normalized matching property} if the bipartite
graph $G_i$ between each pair of successive levels $P_i$ and $P_{i+1}$
has the normalized matching property, for each $i$.
\item A family of
chains ${\cal C}$ (repeated chains allowed) 
is said to be a {\em uniform chain cover} of $P$
if (i) each chain of ${\cal C}$ contains one element from each level and
(ii) for each $p,q \in P$ such that $r(p)=r(q)$,
$p$ and $q$ belong to the same number
of chains of ${\cal C}$.
\item $P$ has the LYM property if
for any antichain $A$, $\sum_{x \in A} \frac{1}{|P_{r(x)}|} \leq 1$.
\end{itemize}
(NOT TO HAND IN:
Prove that if $P$ is a finite connected ranked poset satisfying
the LYM property then $P$ has the Strong Sperner property.)

Prove that the following three conditions
on a ranked poset $P$ are equivalent:

\begin{enumerate}
\item
$P$ has the normalized matching property
\item
$P$ has a uniform chain cover
\item
$P$ has the LYM property.
\end{enumerate}

(Hint on last page.)


\item
\label{cutting edges}
Consider the unit hypercube $C_n$ in $n$ dimensions
which is the convex hull of the set of points $\{0,1\}^n$,
which are the {\em vertices} of $C_n$.
Two vertices $x,y$ are {\em adjacent} in $C_n$ if
they differ in exactly one coordinate.  An edge
of $C_n$ is a line segment joining two adjacent points; for
adjacent $x,y$ the edge joining $x$ and $y$ is denoted $e(x,y)$.
If $a \in R^n$ and $b \in R$, the hyperplane $H_{a,b}$
is the set of points $x \in R^n$ satisfying $a\cdot x=b$.
$H_{a,b}$ is said to {\em slice} the edge $e(x,y)$ if
$x$ and $y$ are on opposite sides of the hyperplane,
i.e., $a\cdot x-b$ and $a \cdot y -b$ are nonzero and have opposite
sign.

\begin{enumerate}
\item
Determine the maximum number of edges that can be sliced by
a single hyperplane. 
(Hint on last page.)

\item
Let $f(n)$ be the minimum number of hyperplanes needed to slice
every edge.  Prove that $f(n) \leq n$ and that $f(n) = \Omega(\sqrt{n})$.
(Note: The lower bound on $f(n)=\Omega(\sqrt{n})$ is the
best currently known.  The upper bound
has been improved slightly to $f(n) \leq \lceil 5n/6 \rceil$.
It is a very nice open problem to improve either of these bounds.)


\end{enumerate}

\item
\label{average size}
Let $n,k$ be positive integers with $n \geq 2k$. 
Suppose ${\cal A}$ is an antichain of $2^{[n]}$ of size
at least $\binom{n}{k}$. Prove that the average size of a member
of ${\cal A}$ is at least $k$.
(Hint on last page.)
 
\item
\begin{enumerate}
\item Prove that if $P$ is a ranked poset with level
sets $P_0,\ldots,P_k$ and $P$ has a symmetric chain decomposition
then $P$ is rank unimodal, rank symmetric, and has the Strong
Sperner property.
\item
Prove that the product of
two symmetric chain orders is a symmetric
chain order.
\item
Prove that the
poset $Div_n$ of divisors of $n$, ordered by
divisibility, is a symmetric chain order.
\end{enumerate}

\item
\label{dichotomy}
Given a subset
$S$ of $\mathbb{R}^d$, a {\em linear dichotomy}
is a partition $(S_1,S_2)$ of $S$ with the property
that there is a pair $(a,b)$ with $a \in \mathbb{R}^d$
and $b \in \mathbb{R}$ such that $\{x \in S:a \cdot x \leq b\}=S_1$.
Prove:
For $S \subseteq \mathbb{R}^d$ of size $n$,
the number of linear dichotomies is at most
$\sum_{j=0}^{d+1} \binom{n}{j}$.
(Hint on last page.)


\item
For a hypergraph ${\cal H}$ on $V$, and $S \subseteq V$,
the {\em neighborhood of $S$ in ${\cal H}$}, denoted $({\cal H}:S)$
is the hypergraph on $V-S$ with $E \in ({\cal H}:S)$ if and only
if $E \cup S \in {\cal H}$. (In particular, the neighborhood
of $\emptyset$ in ${\cal H}$ is just ${\cal H}$ itself.)  
Suppose that ${\cal H}$ is
an $r$-uniform hypergraph, and that for every $S \subseteq V$,
$\tau({\cal H}:S) \leq w$.  Prove ${\cal H}$
has at most $w^r$ edges.


\item
\begin{enumerate}
\item Recall that a sequence of disjoint set pairs (SDSP) is a sequence
$(A_1,B_1),\ldots,(A_t,B_t)$ such that $A_i \cap B_i = \emptyset$.
An SDSP is weakly crossing if for each $i \neq j$
$A_i \cap B_j \neq \emptyset$ or $A_j \cap B_i \neq \emptyset$.
\item  Prove that for a weakly crossing SDSP,
$\sum_{i=1}^t 2^{-|A_i|+|B_i|} \leq 1$.
\item Some preliminaries:
\begin{itemize}
\item A set of points in $\mathbb{R}^d$ is in {\em convex position}
if no one of the points is in the convex hull of the others.
\item A $j$-simplex is the convex hull of $j+1$ distinct points in
convex position. 
\item Warmup problem (not to be handed in): A $d$-simplex 
in $\mathbb{R}^d$ is closed and compact. The boundary of a
$d$-simplex is the
union of $d+1$ $(d-1)$-simplices (called the {\em facets} of the simplex)
having disjoint interiors.
Each facet of the simplex lies in a unique $d-1$-dimensional hyperplane,
which is called a {\em bounding hyperplane} of the simplex.
\item Two $d$-simplexes are said to be {\em adjacent} if
there is a unique $d-1$ dimensional hyperplane containing
their intersection.  (Another warm-up: this hyperplane
must be a bounding hyperplane of both simplexes.)
\end{itemize}
Prove that a collection of $d$-simplexes in $\mathbb{R}^d$
that are pairwise adjacent has size at most $2^{d+1}$.
\end{enumerate}


\item
A {\em closure space} consists of a pair
$(X,\lambda)$ where $X$ is a set and $\lambda:2^X \longrightarrow
2^X$ satisfies:

\begin{itemize}
\item $A \subseteq \lambda(A)$, for all $A \subseteq X$.
\item $A \subseteq B$ implies $\lambda(A) \subseteq \lambda(B)$, for all $A,B \subseteq X$.
\item $\lambda(\lambda(A))=\lambda(A)$.
\end{itemize}
We say that $\lambda$ is a {\em closure on $X$.}
A set $C \in image(\lambda)$ is called a $\lambda$-closed subset.
Define $cl(\lambda)$ to be the set of $\lambda$-closed sets.

A hypergraph $\cal{H}$ on $X$ is called an {\em alignment on $X$}
if (i) $X \in \cal{H}$ and (ii) ${\cal H}$ is closed
under arbitrary intersections: for subset ${\cal H}' \subseteq {\cal H}$,
$\bigcap_{A \in {\cal H}'} A \in {\cal H}$. 

Let $X$ be a fixed (possibly infinite) set.  Prove
that the map that associates each closure $\lambda$ (on $X$)
to $cl(\lambda)$
is a bijection between the set of closures on $X$ to the set of
alignments on $X$.


\item
The K\"onig-Hall theorem says that $\nu({\cal H}=\tau({\cal H})$
if the hypergraph ${\cal H}$  is a bipartite graph.
In this problem and the next we consider the analogous
problem for the class of $k$-uniform $k$-partite hypergraphs.

A $k$-uniform $k$-partite hypergraph ($k$-UP hypergraph) ${\cal H}$
is a hypergraph whose vertex set $V$ is partitioned
into sets $V_1,\ldots,V_k$ such that every edge
contains exactly one element from each set.

It turns out that there are
$k$-UP hypergraphs ${\cal H}$ such that $\nu({\cal H}) < \tau({\cal H})$.
(Warm-up problem, not to be handed in:
Prove that $\tau({\cal H})/\nu({\cal H}) \leq k$ for any
$k$-UP hypergraph ${\cal H}$.)
In this problem we will show that if $q$ is a prime power then
there is a $(q+1)$-UP hypergraphs with $\nu({\cal H})=1$ and $\tau({\cal H})=q$.
The example is based on an important combinatorial/geometric/algebraic structure called
a {\em finite projective plane}.  Abstractly, a finite projective plane
is a hypergraph satisfying the following axioms:  (1) any two edges
intersect in exactly on vertex, (2) for any two vertices
there is a unique edge containing them (3) for some $r$, every edge
has size $r+1$ and every vertex has degree $r+1$.  This structure
is called a finite projective plane of order $r$.

It is known that if $q$ is a prime power then there is a finite
projective plane of order $q$.  This construction will be reviewed
below.  Then we'll construct the desired $(q+1)$-UP hypergraph.
We use the fact that there is exists a finite field of order $q$,
which we'll denote by $\mathbb{F}$.

\begin{enumerate}
\item Consider the vector space $\mathbb{F}^3$, and let $V$ be the
set of one-dimensional subspaces, and $U$ be the set of two-dimensional
subspaces.  Prove that $|V|=|U|=q^2+q+1$.
\item For each $u \in U$, let $E_u$ be the set of one-dimensional
subspaces contained in $u$.  Prove that $\{E_u:u \in U\}$
is a projective plane of order $q$.
\item Now suppose ${\cal P}$ is any finite projective plane of
order $q$ with vertex set $W$.  Construct a hypergraph
${\cal H}$ as follows: fix $v \in W$ and let $V=W-\{v\}$.
Let ${\cal H}$ be the set of edges of ${\cal P}$ that don't
contain $v$.  Prove that ${\cal H}$ is $(q+1)$-partite hypergraph, and
that $\nu({\cal H})=1$ and $\tau({\cal H})=q$.
\end{enumerate}

Remark:  H. Ryser conjectured in the 1960's that for any $k$-UP hypergraph
$\tau({\cal H}) \leq (k-1)\nu({\cal H})$. The case $k=2$ follows
from K\"onig's theorem, and Aharoni proved it for $k=3$ in 1999.
It remains open for all $k \geq 4$.

\end{enumerate}

\begin{center}
{\bf Some hints}
\end{center}
\begin{description}
\item [Problem \ref{LYM}]
Prove $(a) \longrightarrow (b) \longrightarrow (c) \longrightarrow (a)$.
To prove $(a) \longrightarrow (b)$, consider first the case that
all of the levels of $P$ have the same size.  Then generalize 
to the general case.

\item[Problem \ref{cutting edges}] The first part can be reduced
to proving that some poset has the Sperner property.
Further hint: First consider the case that the vector $a$ defining
the hyperplane has all coordinates non-negative.  

\item[Problem \ref{average size}]  
\begin{enumerate}
\item  Argue that it is enough to consider the case $|{\cal H}|=\binom{n}{k}$.
\item Show that the optimal solution of the following LP
is a lower bound on the average size of a member of ${\cal H}$:
Variables $x_0,\ldots,x_n$, $\min 1/\binom{n}{k}\sum_{i} i x_i$
subject to the constraints $\sum_i x_i=\binom{n}{k}$, 
$\sum_i x_i/\binom{n}{i} \leq 1$, and $x_i \geq 0$ for all $i$.
\item Consider the dual LP.
\end{enumerate}
\item[Problem \ref{dichotomy}] It will be helpful to prove
the following: Any set of $d+2$ points in $\mathbb{R}^d$ can be
partitioned into two sets whose convex hulls have nonempty
intersection.  Further hint:  
Let $x_1,\ldots,x_{d+2}$
be the set of points, define $y_1,\ldots,y_{d+1}$
by $y_i=x_i-x_{d+2}$ and note that the $y_i$ are linearly dependent.
Yet another hint: To apply the previous hint, consider the theory
of VC-dimension discussed in class.
\end{description}








\end{document}