1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hall's theorem problem (graph theory)

  1. Mar 1, 2016 #1
    1. The problem statement, all variables and given/known data
    Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King). M

    2. Relevant equations
    Halls theorem IN(A)l>= A
    If this is true for every subset of A then the bipartite graph has a complete matching
    3. The attempt at a solution
    It's too easy. I think. We are going to have a set A which contains the suits and a set B which contains the piles.

    Set A={A,2,3,4,5,6,7,8,9,10,j,q,k}
    Set B={13 piles}

    The trick to prove this is to know that every element in the set A will always have 4 lines going out no matter where, so lN(A)l >=A because no matter which subset of the set A we pick, every vertex in the set A will always have 4 neighbors and intuitively the addition of those neighbors will be always greater that the number of vertices or elements in A

    As easy as that?
     
  2. jcsd
  3. Mar 2, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Unfortunately not.
    Given two elements in A, their neighbours in B can overlap, so there will not necessarily be eight neighbours.
    You have to find some way of putting a lower bound on the number of neighbours in B that a set ##W\subseteq A## has.
    Given we're starting with a ratio of four to one, one would imagine ('intuitively' as you say) that for any W, the neighbours can't overlap so badly that the number of neighbours is less than |W|. But imagining is one thing, and proof is another.
     
  4. Mar 2, 2016 #3
    How do they overlap?, each pile can't have more than 4 cards. Can you show an example of why my proof doesn't work?. I would appreciate it.
     
  5. Mar 2, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Say pile 1 contains two black aces and two black twos, and
    pile 2 contains two red aces and two red twos.

    Then the set of all neighbours of elements of W={Ace, 2}##\subset##A comprises only two elements {Pile 1, Pile 2} of set B.
     
  6. Mar 2, 2016 #5
    I am trying to understand your point. Yes, they overlap and in this case the number of neighbors of the set {Ace,2} is 8, so the inequality is satisfied. Each box contains 4 slots. I am not saying that each suit must perfectly math each box. That would be silly. Each box can be seen as a component of the graph.
     
  7. Mar 2, 2016 #6
    E
    I don't know if in this case we can consider each component as a vertex and allow edge repetitions among components.
     
  8. Mar 2, 2016 #7
    Correct Andrewirk, I saw my mistake. I am just wondering if we can do this by considering the lower bound as you stated. For example, the minimum number of neighbors of each label has to be 1. If we do this to every subset of A, we will notice that lN(A)l =A for the lower bound. But I am still worried because the theorem doesn't say that the matching will cover both sides of the graph. This is what it says:
     
  9. Mar 2, 2016 #8

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    In general that would be a problem, but not in this case.
    Why? Because sets A and B have the same number of elements, and one side - assume wlog it is A - is covered by the matching. Since every element in A is at one end of an edge in the matching, and an element of B is at the other end, and the definition of a 'matching' requires that every element of B is at the end of at most one matching, what can we conclude about the coverage of B?
     
  10. Mar 2, 2016 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Quite so. But in any case, the theorem does not conclude there is a matching for "at least one side". The conditions are not symmetric. The side that is guaranteed a matching is prescribed.
     
  11. Mar 3, 2016 #10
    I don't get it. It gives a necessary and sufficient condition for finding a matching that covers at least one side of the graph.
     
  12. Mar 3, 2016 #11

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    As haruspex said, the theorem is asymmetric. It says, that, IF one side of the graph obeys the condition ##|W|\leq |N_G(W)|## (using the notation from this wiki page) then there is a matching that covers THAT side of the graph. It doesn't just say the matching covers one of the two sides, unspecified.
     
  13. Mar 3, 2016 #12
    So can't we do this by using hall's theorem?
     
  14. Mar 3, 2016 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Hall's theorem will certainly give you the result you need, in either of two ways.
    You are asked to show that all ranks can be matched by selections of piles. To get that result directly from Hall you need to show that every subset of the ranks spans at least as many piles.
    If, instead, you were to show that every subset of piles spans at least as many ranks, you would then need to use Andrew's observation in post #8 to flip it around to the result you need.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Hall's theorem problem (graph theory)
  1. Graph theory problem (Replies: 17)

Loading...