Matchings in bipartite graphs and systems of distinct representatives (SDRs) of systems of subsets are closely related. More precisely, let for a finite set. We can construct a bipartite graph where

An SDR of is such that for all and for all In particular contains exactly one element for each

Then is a matching of saturating the part In particular, it is a maximum matching.

Conversely, a matching of saturating gives rise to an SDR for

An obvious necessary condition for existing of an SDR for

is the following **Hall’s condition**:

In view of this, Hall’s Theorem for matchings is equivalent to the following

An SDR for exists iff it satisfies Hall’s condition.

To see that Hall’s condition is sufficient, we proceed by induction on For the claim is obvious. Assume that it is true for all collections of less than sets. We now establish that it holds for -set collections, too.

If then we take any and set for some Now by induction there is an SDR for Then is an SDR for

In the remaining case there exists such that By induction, there is an SDR for

Let Then for otherwise contradicting Hall’s condition. Now we can take an SDR for and observe that is an SDR for

### Like this:

Like Loading...

*Related*

Tags: combinatorics, graph theory, MAS324, teaching

This entry was posted on 14 September, 2009 at 12:05 and is filed under undergrad maths. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply