In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations:
* The
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
formulation deals with a collection of
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
sets. It gives a necessary and sufficient condition for being able to select a distinct element from each set.
* The
graph theoretic formulation deals with a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
. It gives a necessary and sufficient condition for finding a
matching that covers at least one side of the graph.
Combinatorial formulation
Statement
Let
be a
family
Family (from la, familia) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its ...
of
finite sets
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
. Here,
is itself allowed to be infinite (although the sets in it are not) and to 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
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
of an
injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
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:
Examples
;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
. Because this family has at least one transversal, the marriage condition is met. Every subfamily of
has equal size to the set of representatives it is mapped to, which is less than or equal to the size of the union of the subfamily.
;Example 2
: Consider
with
No valid transversal exists; the marriage condition is violated as is shown by the subfamily
. Here the number of sets in the subfamily is
, while the union of the three sets
contains only two elements.
Graph theoretic formulation
Let
be a finite
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
with bipartite sets
and
and edge set
. An ''
-perfect matching'' (also called an ''
-saturating matching'') is a
matching, a set of disjoint edges, which covers every vertex in
.
For a subset
of
, let
denote the
neighborhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...
of
in
, the set of all vertices in
that are
adjacent to at least one element of
. The marriage theorem in this formulation states that there is an
-perfect matching
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
for every subset
of
:
In other words, every subset
of
must have sufficiently many neighbors in
.
Proof of the graph theoretic version
;Easy direction
: In an
-perfect matching
, every edge incident to
connects to a distinct neighbor of
in
, so the number of these matched neighbors is at least
. The number of all neighbors of
is at least as large.
;Hard direction
: The theorem can be proven if the assumption that there is no
-perfect matching leads to the conclusion that Hall's condition is violated for at least one
. Let
be a maximum matching, and let
be any unmatched vertex in
. Consider all ''alternating paths'' (paths in
that alternately use edges outside and inside
) starting from
. Let
be the set of vertices in these paths that belong to
(including
itself) and let
be the set of vertices in these paths that belong to
. Then every vertex in
is matched by
to a vertex in
, because an alternating path to an unmatched vertex could be used to increase the size of the matching by toggling whether each of its edges belongs to
or not. Therefore, the size of
is at least the number
of these matched neighbors of
, plus one for the unmatched vertex
. That is,
. However, for every vertex
, every neighbor
of
belongs to
: an alternating path to
can be found either by removing the matched edge
from the alternating path to
, or by adding the unmatched edge
to the alternating path to
. Therefore,
and
, showing that Hall's condition is violated.
Equivalence of the combinatorial formulation and the graph-theoretic formulation
A problem in the combinatorial formulation, defined by a finite family of finite sets
with union
can be translated into a bipartite graph
where each edge connects a set in
to an element of that set. An
-perfect matching in this graph defines a system of unique representatives for
. In the other direction, from any bipartite graph
one can define a finite family of sets, the family of neighborhoods of the vertices in
, such that any system of unique representatives for this family corresponds to an
-perfect matching in
. In this way, the combinatorial formulation for finite families of finite sets and the graph-theoretic formulation for finite graphs are equivalent.
The same equivalence extends to infinite families of finite sets and to certain infinite graphs. In this case, the condition that each set be finite corresponds to a condition that in the bipartite graph
, every vertex in
should have finite
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
. The degrees of the vertices in
are not constrained.
Topological proof
Hall's theorem can be proved (non-constructively) based on
Sperner's lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an ...
.
Applications
The theorem has many applications. For example, for a
standard deck of cards, dealt into 13 piles of 4 cards each, the marriage theorem implies that it is possible to select one card from each pile so that the selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King). More generally, any
regular bipartite graph has a perfect matching.
More abstractly, let
be a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
, and
be a finite
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
of
. Then the marriage theorem can be used to show that there is a set
such that
is a transversal for both the set of left
coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
s and right cosets of
in
.
The marriage theorem is used in the usual proofs of the fact that an
Latin rectangle In combinatorial mathematics, a Latin rectangle is an matrix (where ), using symbols, usually the numbers or as its entries, with no number occurring more than once in any row or column.
An Latin rectangle is called a Latin square.
An example ...
can always be extended to an
Latin rectangle when