Hall's Marriage Theorem
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations. In each case, the theorem gives a
necessary and sufficient In logic and mathematics, necessity and sufficiency are terms used to describe a material conditional, conditional or implicational relationship between two Statement (logic), statements. For example, in the Conditional sentence, conditional stat ...
condition for an object to exist: * The
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
formulation answers whether a
finite Finite may refer to: * 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 marked for person and/or tense or aspect * "Finite", a song by Sara Gr ...
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 In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
has a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
—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 A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neighbourh ...
of equal or greater size.


Combinatorial formulation


Statement

Let \mathcal F be a finite
family Family (from ) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). It forms the basis for social order. Ideally, families offer predictabili ...
of sets (note that although \mathcal F is not itself allowed to be infinite, the sets in it may be so, and \mathcal F may contain the same set multiple times). Let X be the union of all the sets in \mathcal F, the set of elements that belong to at least one of its sets. A transversal for \mathcal F is a subset of X that can be obtained by choosing a distinct element from each set in \mathcal F. This concept can be formalized by defining a transversal to be the
image An image or picture is a visual representation. An image can be Two-dimensional space, two-dimensional, such as a drawing, painting, or photograph, or Three-dimensional space, three-dimensional, such as a carving or sculpture. Images may be di ...
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 of its codomain; that is, implies (equivalently by contraposition, impl ...
f:\mathcal F\to X such that f(S)\in S for each S\in\mathcal F. An alternative term for ''transversal'' is ''system of distinct representatives''. The collection \mathcal F satisfies the marriage condition when each subfamily of \mathcal F contains at least as many distinct members as its number of sets. That is, for all \mathcal G \subseteq \mathcal F, , \mathcal G, \le\Bigl, \bigcup_ S\Bigr, . If a transversal exists then the marriage condition must be true: the function f used to define the transversal maps \mathcal G to a subset of its union, of size equal to , \mathcal G, , so the whole union must be at least as large. Hall's theorem states that the converse is also true: The name "marriage theorem" came from
Suppose that each of a (possibly infinite) set of boys is acquainted with a finite set of girls. Under what conditions is it possible for each boy to marry one of his acquaintances? It is clearly necessary that every finite set of ''k'' boys be, collectively, acquainted with at least ''k'' girls... this condition is also sufficient.


Examples

;Example 1 : Consider the family \mathcal F=\ with X=\ and \begin A_1&=\\\ A_2&=\\\ A_3&=\.\\ \end The transversal \ could be generated by the function that maps A_1 to 1, A_2 to 5, and A_3 to 3, or alternatively by the function that maps A_1 to 3, A_2 to 1, and A_3 to 5. There are other transversals, such as \ and \. Because this family has at least one transversal, the marriage condition is met. Every subfamily of \mathcal F 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 \mathcal F=\ with \begin A_1&=\\\ A_2&=\\\ A_3&=\\\ A_4&=\.\\ \end No valid transversal exists; the marriage condition is violated as is shown by the subfamily \mathcal G=\. Here the number of sets in the subfamily is , \mathcal G, =3, while the union of the three sets A_2\cup A_3\cup A_4=\ contains only two elements. A lower bound on the different number of transversals that a given finite family \mathcal F of size n may have is obtained as follows: If each of the sets in \mathcal F has cardinality \geq r, then the number of different transversals for \mathcal F is either r! if r\leq n, or r(r-1)\cdots(r-n+1) if r>n. Recall that a transversal for a family \mathcal F is an ordered sequence, so two different transversals could have exactly the same elements. For instance, the collection A_=\, A_=\ has (1, 2) and (2, 1) as distinct transversals.


Graph theoretic formulation

Let G=(X,Y,E) be a finite
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
with bipartite sets X and Y and edge set E. An ''X-perfect matching'' (also called an ''X-saturating matching'') is a matching, a set of disjoint edges, which covers every vertex in X. For a subset W of X, let N_G(W) denote the
neighborhood A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of W in G, the set of all vertices in Y that are adjacent to at least one element of W. The marriage theorem in this formulation states that there is an X-perfect matching
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
for every subset W of X: , W, \leq , N_G(W), . In other words, every subset W of X must have sufficiently many neighbors in Y.


Proof


Necessity

In an X-perfect matching M, every edge incident to W connects to a distinct neighbor of W in Y, so the number of these matched neighbors is at least , W, . The number of all neighbors of W is at least as large.


Sufficiency

Consider the
contrapositive In logic and mathematics, contraposition, or ''transposition'', refers to the inference of going from a Conditional sentence, conditional statement into its logically equivalent contrapositive, and an associated proof method known as . The contrap ...
: if there is no X-perfect matching then Hall's condition must be violated for at least one W\subseteq X. Let M be a maximum matching, and let u be any unmatched vertex in X. Consider all ''alternating paths'' (paths in G that alternately use edges outside and inside M) starting from u. Let W be the set of vertices in these paths that belong to X (including u itself) and let Z be the set of vertices in these paths that belong to Y. Then every vertex in Z is matched by M to a vertex in W, 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 M or not. Therefore, the size of W is at least the number , Z, of these matched neighbors of Z, plus one for the unmatched vertex u. That is, , W, \ge , Z, +1. However, for every vertex v\in W, every neighbor w of v belongs to Z: an alternating path to w can be found either by removing the matched edge vw from the alternating path to v, or by adding the unmatched edge vw to the alternating path to v. Therefore, Z=N_G(W) and , W, \ge , N_G(W), +1, 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 \mathcal F with union X can be translated into a bipartite graph G=(\mathcal F,X,E) where each edge connects a set in \mathcal F to an element of that set. An \mathcal F-perfect matching in this graph defines a system of unique representatives for \mathcal F. In the other direction, from any bipartite graph G=(X,Y,E) one can define a finite family of sets, the family of neighborhoods of the vertices in X, such that any system of unique representatives for this family corresponds to an X-perfect matching in G. 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 G=(X,Y,E), every vertex in X should have finite degree. The degrees of the vertices in Y 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). This can be done by constructing a bipartite graph with one partition containing the 13 piles and the other partition containing the 13 ranks. The remaining proof follows from the marriage condition. More generally, any
regular Regular may refer to: Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instruments, tunings with equal intervals between the paired notes of successive open strings Other uses * Regular character, ...
bipartite graph has a perfect matching. More abstractly, let G 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 iden ...
, and H be a finite
index Index (: indexes or 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 the Halo Array in the ...
subgroup In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation  ...
of G. Then the marriage theorem can be used to show that there is a set T such that T 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 H in G. The marriage theorem is used in the usual proofs of the fact that an r\times n
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. Latin rec ...
can always be extended to an (r+1)\times n Latin rectangle when r, and so, ultimately to a
Latin square Latin ( or ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken by the Latins in Latium (now known as Lazio), the lower Tiber area around Rome, Italy. Through the expansion o ...
.


Logical equivalences

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include: * The König–Egerváry theorem (1931) (
Dénes Kőnig Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of Hungarian Jewish heritage who worked in and wrote the first textbook on the field of graph theory. Biography Kőnig was born in Budapest, the son of mathemat ...
, Jenő Egerváry) * König's theorem *
Menger's theorem In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in ...
(1927) * The
max-flow min-cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...
(Ford–Fulkerson algorithm) * The
Birkhoff–Von Neumann theorem In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e., :\sum_i x_=\sum_j x_= ...
(1946) *
Dilworth's theorem In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all ...
. In particular, there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.


Infinite families


Marshall Hall Jr. variant

By examining
Philip Hall Philip Hall FRS (11 April 1904 – 30 December 1982), was an English mathematician. His major work was on group theory, notably on finite groups and solvable groups. Biography He was educated first at Christ's Hospital, where he won the Thom ...
's original proof carefully, Marshall Hall Jr. (no relation to Philip Hall) was able to tweak the result in a way that permitted the proof to work for infinite \mathcal F. This variant extends Philip Hall's Marriage theorem. Suppose that \mathcal F = \_, is a (possibly infinite) family of finite sets that need not be distinct, then \mathcal F has a transversal if and only if \mathcal F satisfies the marriage condition.


Marriage condition does not extend

The following example, due to Marshall Hall Jr., shows that the marriage condition will not guarantee the existence of a transversal in an infinite family in which infinite sets are allowed. Let \mathcal F be the family, A_=\mathbb N, A_=\ for i\geq 1. The marriage condition holds for this infinite family, but no transversal can be constructed.


Graph theoretic formulation of Marshall Hall's variant

The graph theoretic formulation of Marshal Hall's extension of the marriage theorem can be stated as follows: Given a bipartite graph with sides ''A'' and ''B'', we say that a subset ''C'' of ''B'' is smaller than or equal in size to a subset ''D'' of ''A'' ''in the graph'' if there exists an injection in the graph (namely, using only edges of the graph) from ''C'' to ''D'', and that it is strictly smaller in the graph if in addition there is no injection in the graph in the other direction. Note that omitting ''in the graph'' yields the ordinary notion of comparing cardinalities. The infinite marriage theorem states that there exists an injection from ''A'' to ''B'' in the graph, if and only if there is no subset ''C'' of ''A'' such that ''N''(''C'') is strictly smaller than ''C'' in the graph. The more general problem of selecting a (not necessarily distinct) element from each of a collection of
non-empty In mathematics, the empty set or void set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, whil ...
sets (without restriction as to the number of sets or the size of the sets) is permitted in general only if the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
is accepted.


Fractional matching variant

A ''fractional matching'' in a graph is an assignment of non-negative weights to each edge, such that the sum of weights adjacent to each vertex is at most 1. A fractional matching is ''X''-perfect if the sum of weights adjacent to each vertex is exactly 1. The following are equivalent for a bipartite graph ''G'' = (''X+Y, E''): * ''G'' admits an X-perfect matching. * ''G'' admits an X-perfect fractional matching. The implication follows directly from the fact that ''X''-perfect matching is a special case of an ''X''-perfect fractional matching, in which each weight is either 1 (if the edge is in the matching) or 0 (if it is not). * ''G'' satisfies Hall's marriage condition. The implication holds because, for each subset ''W'' of ''X'', the sum of weights near vertices of ''W'' is , ''W'', , so the edges adjacent to them are necessarily adjacent to at least '', W, '' vertices of ''Y''.


Quantitative variant

When Hall's condition does not hold, the original theorem tells us only that a perfect matching does not exist, but does not tell what is the largest matching that does exist. To learn this information, we need the notion of deficiency of a graph. Given a bipartite graph ''G'' = (''X''+''Y'', ''E''), the ''deficiency of G w.r.t. X'' is the maximum, over all subsets ''W'' of ''X'', of the difference , ''W'', - , ''N''''G''(''W''), . The larger is the deficiency, the farther is the graph from satisfying Hall's condition. Using Hall's marriage theorem, it can be proved that, if the deficiency of a bipartite graph ''G'' is ''d'', then ''G'' admits a matching of size at least , ''X'', -''d''.


Generalizations

* A characterization of perfect matchings in general graphs (that are not necessarily bipartite) is provided by the
Tutte theorem In the mathematical discipline of graph theory, the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings. It is a special case of the Tutte–Berge formula. Intuition The g ...
. * A generalization of Hall's theorem to bipartite hypergraphs is provided by various
Hall-type theorems for hypergraphs In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, ...
.


Notes


References

* * * * * * * *


External links


Marriage Theorem
at
cut-the-knot Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet Union, Soviet-born Israeli Americans, Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow ...

Marriage Theorem and Algorithm
at
cut-the-knot Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet Union, Soviet-born Israeli Americans, Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow ...

Hall's marriage theorem explained intuitively
at Lucky's notes. {{PlanetMath attribution, id=3059, title=proof of Hall's marriage theorem Matching (graph theory) Theorems in combinatorics Theorems in graph theory Articles containing proofs