\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\ca}{{\cal A}}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2011/12/05 before class

\begin{center}
{\LARGE\bf Homework 11}
\end{center}

\begin{hw} Let $\ca$ be a set of $(r+1)$-subsets of $[n]$, i.e., $\ca \subseteq \binom{[n]}{r+1}$.
Its {\em shadow} is defined as
\[
\partial \ca = \{ B \in \binom{[n]}{r} : \exists A \in \ca, B \subseteq A.\}
\]
Prove that the proportion of $\partial \ca$ in its level is at least as big as the proportion
of $\ca$ in level $(r+1)$, i.e.,
\[
\frac{\partial \ca}{\binom{n}{r}} \geq \frac{\ca}{\binom{n}{r+1}}.
\]
\end{hw}

\begin{hw} A chain of sets $A_1 \subseteq A_2 \subseteq ... \subseteq A_t$ is $n$-symmetric
if $|A_{i+1}| = |A_i| + 1$ for any $1 \leq i < t$, and $|A_1| + |A_t| = n$.

Partition the poset $2^{[4]}$ into $4$-symmetric chains.

(Think about this: Prove that we can partition $2^{[n]}$ into
$n$-symmetric chains.)
\end{hw}

\begin{hw} Let $n=10$, consider subsets of $[n]$.

(a) Are there 200 subsets $(A_1, A_2, ..., A_{200})$ such that $A_i \not\subseteq A_j$ for any $i \neq j$?

(b) Are there 100 subsets $(B_1, B_2, ..., B_{100})$ such that $|B_i| = 5$ for all $i$, and $B_i \cap B_j \neq \emptyset$ for all $i < j$?
\end{hw}

\begin{hw}
A matrix with integer entries is called good if no row nor column contains the same number
twice.

Let $A$ be a $k \times n$ good matrix ($k < n$) with entries from $[n]$, prove that there is an $n \times n$ good matrix $B$ with entries from $[n]$ such that the first $k$ rows of $B$ is identical to $A$.
\end{hw}

\end{document}

