Hall's marriage theorem

The marriage set, or set of Hall, named after Philip Hall, is a mathematical theorem from combinatorics and the theory of finite sets from the year 1935. Considered as the starting point of matching theory in graph theory.

Problem

Given from a finite set and a finite number of subsets that do not necessarily all have to be different. Is it possible to select elements such that they are all different?

The following folkloric interpretation led to the widely - spread term marriage set. Given a lot of marriageable women and a lot of to eligible men. For every woman be the set of preferred by men. Can you now set up a mass wedding so that all women marry a man preferred? For each woman to a man to choose and at the prevailing monogamy no two women can marry the same man, that is, the selected men must be pairwise different.

If there is a choice of the type required, so there must be a suitable for each subset to each index, so the are pairwise different, and in particular it must therefore give in at least many elements, the number of elements in designated. So The existence of a selection of the type required we obtain the following necessary conditions, which are also called the Hall conditions:

Marriage theorem

The marriage record states that the Hall conditions for the existence of a selection are also sufficient:

There are a finite set and subsets of. Then the following statements are equivalent:

• There are such that the are pairwise different.
• The Hall conditions are met.

A proof can be performed by means of induction on the number of sets. A short proof can be found in.

Graph Theory

The Marriage Hall's theorem can be summarized as follows graph-theoretical point. It is a bipartite graph with bipartition. A matching is a set of different edges that have no vertices of the graph together. For a subset is the set of all adjacent to points that are a subset of because of Bipartitheit necessarily. The question of a matching, where all the nodes occur, is the question of a choice of pairwise distinct nodes for all. The marriage rate is in this context:

For a bipartite graph with bipartition following statements are equivalent:

• There is a matching, in which each node occurs from.
• For all subsets.