# Hall's theorem problem (graph theory)

1. Mar 1, 2016

### TheMathNoob

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. Mar 2, 2016

### andrewkirk

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.

3. Mar 2, 2016

### TheMathNoob

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.

4. Mar 2, 2016

### andrewkirk

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.

5. Mar 2, 2016

### TheMathNoob

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.

6. Mar 2, 2016

### TheMathNoob

E
I don't know if in this case we can consider each component as a vertex and allow edge repetitions among components.

7. Mar 2, 2016

### TheMathNoob

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:

8. Mar 2, 2016

### andrewkirk

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?

9. Mar 2, 2016

### haruspex

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.

10. Mar 3, 2016

### TheMathNoob

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.

11. Mar 3, 2016

### andrewkirk

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.

12. Mar 3, 2016

### TheMathNoob

So can't we do this by using hall's theorem?

13. Mar 3, 2016

### haruspex

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.