Help with Graph theory problem

**qwesl** · January 18th 2010, 12:37 PM

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.

**NonCommAlg** · January 18th 2010, 09:53 PM

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.

Thread: Help with Graph theory problem

LinkBack

Thread Tools

Display

Help with Graph theory problem

Similar Math Help Forum Discussions

Graph theory problem

Graph Theory Problem

Graph Theory problem

please help~~graph theory problem

Help with Graph Theory problem

Search Tags