Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Hall's marriage theorem
Summary
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:
The combinatorial formulation answers whether a finite collection of sets has a transversal—that is, whether an element can be chosen from each set without repetition. Hall's condition is that for any group of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the group.
The graph theoretic formulation answers whether a finite bipartite graph has a perfect matching—that is, a way to match each vertex from one group uniquely to an adjacent vertex from the other group. Hall's condition is that any subset of vertices from one group has a neighbourhood of equal or greater size.
Let be a finite family of sets (note that although is not itself allowed to be infinite, the sets in it may be so, and may contain the same set multiple times). Let be the union of all the sets in , the set of elements that belong to at least one of its sets. A transversal for is a subset of that can be obtained by choosing a distinct element from each set in . This concept can be formalized by defining a transversal to be the of an injective function such that for each . An alternative term for transversal is system of distinct representatives.
The collection satisfies the marriage condition when each subfamily of contains at least as many distinct members as its number of sets. That is, for all ,
If a transversal exists then the marriage condition must be true: the function used to define the transversal maps to a subset of its union, of size equal to , so the whole union must be at least as large. Hall's theorem states that the converse is also true:
Example 1
Consider the family with and The transversal could be generated by the function that maps to , to , and to , or alternatively by the function that maps to , to , and to . There are other transversals, such as and .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.