# Thread: Help with Graph theory problem

1. ## Help with Graph theory problem

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

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

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

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