Results 1 to 2 of 2

Math Help - Help with Graph theory problem

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    25

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by qwesl View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  3. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 12:50 PM
  4. please help~~graph theory problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 19th 2008, 05:20 AM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 10:08 PM

Search Tags


/mathhelpforum @mathhelpforum