# Math Help - Help with Graph theory problem

1. ## Help with Graph theory problem

Suppose $S=\{1,2,..,n\}$ and $0\le k \le \frac{n}{2}$. Suppose $A$ is a collection of all $k$-element subsets of $S$ and let $B$ be the collection of all $(k+1)$-element subsets of $S$. Build a bipartite graph $G=(V,E)$ with $V=A\cup B$ by joining $X\in A$ to $Y\in B$ if and only if $X\subset Y$

Suppose $Z$ is a collection of subsets of $S$ such that for all distinct $X,Y\in Z, X\nsubseteq Y$ and $Y\nsubseteq X$. Show that $\mid Z\mid \le \binom{n}{\lfloor \frac{n}{2} \rfloor}$.

Hint 1: First show $G$ has a matching hitting every element of $A$
Hint 2: If $Z$ consists of all subsets of $S$ of size $\lfloor \frac{n}{2} \rfloor$ then this upper bound is reached.

2. Originally Posted by qwesl
Suppose $Z$ is a collection of subsets of $S$ such that for all distinct $X,Y\in Z, X\nsubseteq Y$ and $Y\nsubseteq X$. Show that $\mid Z\mid \le \binom{n}{\lfloor \frac{n}{2} \rfloor}$.
see Sperner's lemma.