\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,epsfig,anysize}

\def\arrow{\to}
\def\cross{\times}
\def\Intersect{\bigcap}

\def\comb#1#2{\left(
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right) }

\def\part#1#2{\left\{
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right\} }

\def\cycle#1#2{\left[
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right] }


\def\rmand{\mbox{ and }}

\pagestyle{empty}

\begin{document}


\begin{flushleft}
          Fall 93\\
          Math 475 \\
          A.Miller
\end{flushleft}


       Due  Mon Dec 6

       Homework assignment   Chapter 9  p. 330-335

\bigskip

\centerline{  7 8 9 12 13 14 15 16}

\vspace{.5in}

(A)  Let $\langle A_1, A_2,\ldots, A_n\rangle$ be a sequence
of sets such that for some positive integer $p$,
\begin{enumerate}
  \item $|A_i|\geq p$ for each $i=1,2,\ldots, n$ and
  \item any intersection of more than $p$ of the $A_i$'s is empty, i.e.,
   for every  $Q\subseteq\{1,2,\ldots,n\}$ with $|Q|=p+1$ the
   intersection is empty:
   $$\Intersect_{i\in Q}A_i=\emptyset.$$
\end{enumerate}
Show that $\langle A_1, A_2,\ldots, A_n\rangle$ has a SDR.

\bigskip

(B) A Latin rectangle is an $m \cross n$ matrix with $m\leq n$ whose
rows are each a permutation of $1,2,\ldots,n$ and whose columns are
lists of $m$ distinct integers.  Let $B_{m\cross n}$ be a Latin rectangle
with $m<n$.  By using an SDR for the sets of numbers not used in
each column, show that $B$ can be extended to an $(m+1)\cross n$
Latin rectangle.  (Hint: use problem (A) with $p=n-m$)

\bigskip

(C) Let $X$ be a set of size $n$ and let $k<n/2$.  Define
$$B=\{A\subseteq X: |A|=k\}$$
$$G=\{A\subseteq X: |A|=k+1\}$$
$$K=\{(A_0,A_1)\in B\cross G: A_0\subseteq A_1\}$$
Show that in the bipartite graph the degree of every element of
$B$ is $n-k$ and the degree of every element of $G$ is $k+1$.
Conclude that $K$ contains a matching.  (This exercise can
be used to give another proof of Sperner's Theorem.)





\end{document}