Hall's theorem problem (graph theory)

[TheMathNoob]

Homework Statement

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

Homework Equations

Halls theorem IN(A)l>= A
If this is true for every subset of A then the bipartite graph has a complete matching

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?

 

[andrewkirk]

As easy as that?

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.

 

[TheMathNoob]

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.

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.

 

[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.

 

[TheMathNoob]

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.

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.

 

[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.

E

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.

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.

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

 

[TheMathNoob]

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.

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:

• The graph theoretic formulation deals with a bipartite graph. It gives a necessary and sufficient condition for finding a matching that covers at least one side of the graph.

 

[andrewkirk]

I am still worried because the theorem doesn't say that the matching will cover both sides of the graph.

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?

 

[haruspex]

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?

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.

 

[TheMathNoob]

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.

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.

 

[andrewkirk]

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.

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.

 

[TheMathNoob]

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.

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

 

[haruspex]

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

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.