In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), 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.
Combinatorial formulation
Statement
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).[1] 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 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:
Hall's Marriage Theorem — A family of finite sets has a transversal if and only if satisfies the marriage condition.
Examples
example 1, marriage condition met
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, marriage condition violated
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.
A lower bound on the different number of transversals that a given finite family of size may have is obtained as follows: If each of the sets in has cardinality , then the number of different transversals for is either if , or if .[2]
Recall that a transversal for a family is an ordered sequence, so two different transversals could have exactly the same elements. For instance, the collection , has and as distinct transversals.
Graph theoretic formulation
blue edges represent a matching
Let be a finite bipartite graph 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 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 for every subset of : In other words, every subset of must have sufficiently many neighbors in .
Proof
Necessity
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.
Sufficiency
Consider the contrapositive: if there is no -perfect matching then Hall's condition must be 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. The degrees of the vertices in are not constrained.
Topological proof
Hall's theorem can be proved (non-constructively) based on Sperner's lemma.[3]: Thm.4.1, 4.2
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 bipartite graph has a perfect matching.[4]: 2
More abstractly, let be a group, and be a finite indexsubgroup 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 cosets and right cosets of in .[5]
The marriage theorem is used in the usual proofs of the fact that an Latin rectangle can always be extended to an Latin rectangle when , and so, ultimately to a Latin square.[6]
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:
In particular,[8][9] 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'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 .[10] This variant extends Philip Hall's Marriage theorem.
Suppose that , is a (possibly infinite) family of finite sets that need not be distinct, then has a transversal if and only if 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 be the family, , for . The marriage condition holds for this infinite family, but no transversal can be constructed.[11]
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 Ain 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.[12]
The more general problem of selecting a (not necessarily distinct) element from each of a collection of non-empty 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 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):[13]
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.
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| - |NG(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.
^Hall 1986, pg. 51. An alternative form of the marriage theorem applies to finite families of sets that can be infinite. However, the situation of having an infinite number of sets while allowing infinite sets is not allowed.
^Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano (2014). "Coset Intersection Graphs for Groups". The American Mathematical Monthly. 121 (10): 922–26. arXiv:1304.6111. doi:10.4169/amer.math.monthly.121.10.922. S2CID16417209. For a finite index subgroup of , the existence of a left-right transversal is well known, sometimes presented as an application of Hall's marriage theorem.
^The naming of this theorem is inconsistent in the literature. There is the result concerning matchings in bipartite graphs and its interpretation as a covering of (0,1)-matrices. Hall (1986) and van Lint & Wilson (1992) refer to the matrix form as König's theorem, while Roberts & Tesman (2009) refer to this version as the Kőnig-Egerváry theorem. The bipartite graph version is called Kőnig's theorem by Cameron (1994) and Roberts & Tesman (2009).
^Aharoni, Ron (February 1984). "König's Duality Theorem for Infinite Bipartite Graphs". Journal of the London Mathematical Society. s2-29 (1): 1–12. doi:10.1112/jlms/s2-29.1.1. ISSN0024-6107.
Pierre AlechinskyPierre Alechinsky (1965)Lahir19 Oktober 1927 (umur 96)Schaerbeek, BelgiaKebangsaanBelgianDikenal atasLukisan, Seni Cetak, Menggambar Pierre Alechinsky (lahir 19 Oktober 1927) adalah seorang seniman Belgia. Ia tinggal dan bekerja di Prancis sejak 1951. Karyanya berkaitan dengan tachisme, ekspresionisme abstrak, dan abstraksi liris. Biografi Alechinsky lahir di Schaerbeek. Pada tahun 1944 ia menghadiri l'École nationale supérieure d'Architecture et des Arts decoratifs de La…
Questa voce sull'argomento università del Giappone è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Università di Kanagawa Dati generaliFondazione1928 FondatoreYoshimori Yoneda Tipouniversità PresidenteYoshio Kaneko Mappa di localizzazione Sito web Modifica dati su Wikidata · Manuale L'università di Kanagawa è un'università privata del Giappone. La sede del campus si trova a Kanagawa-ku, uno dei quartieri di Yokohama, nella prefettura di Kanaga…
This is a list of notable people from the city of Karachi in Pakistan, also known as Karachiites: Karachi This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by adding missing items with reliable sources. Armed forces Vice Admiral Syed Mohammad Ahsan - governor Muhammad Mahmood Alam Mirza Aslam Beg - four-star general Moinuddin Haider - lieutenant general, governor Pervez Musharraf - former President and Army Chief of Pakistan Ft. Lt. Rashi…
William Seward served as Secretary of State from 1861 to 1869 The history of U.S. foreign policy from 1861 to 1897 concerns the foreign policy of the United States during the presidential administrations of Abraham Lincoln, Andrew Johnson, Ulysses S. Grant, Rutherford B. Hayes, James A. Garfield, Chester A. Arthur, Grover Cleveland, and Benjamin Harrison. The period began with the outbreak of the American Civil War 1861 and ended with the 1897 inauguration of William McKinley, whose administrati…
Municipality in Southeast, BrazilSerraMunicipalityThe Municipality of SerraThe Mestre Álvaro seen the BR-101 between Planalto Serrano and Vista da Serra II FlagSealLocalization of Serra in Espirito SantoSerraLocalization of Serra, Espirito Santo in BrazilCoordinates: 20°07′44″S 40°18′28″W / 20.12889°S 40.30778°W / -20.12889; -40.30778Country BrazilRegionSoutheastState Espírito SantoFoundedNovember 6, 1556Government • MayorAudifax Barcellos(P…
Cuautitlán Gemeente in Mexico Situering Staat Mexico Hoofdplaats Cuautitlán Coördinaten 19°40'19,99NB, 99°10'50,02WL Gegevens Oppervlakte 37,3 km² Inwoners 75.831 (2000) Website Officiële site E-Local Portaal Mexico Cuautitlán is een gemeente in de Mexicaanse deelstaat Mexico. De hoofdplaats van Cuautitlán is Cuautitlán. De gemeente Cuautitlán heeft een oppervlakte van 37,3 km². De gemeente heeft 75.831 inwoners (2000). 400 daarvan spreken een indiaanse taal,…
Russland Nail Jakupow Geburtsdatum 6. Oktober 1993 Geburtsort Nischnekamsk, Russland Größe 181 cm Gewicht 86 kg Position Rechter Flügel Nummer #10 Schusshand Links Draft KHL Junior Draft 2010, 1. Runde, 19. PositionNeftechimik Nischnekamsk NHL Entry Draft 2012, 1. Runde, 1. PositionEdmonton Oilers Karrierestationen bis 2010 Neftechimik Nischnekamsk 2010–2012 Sarnia Sting 2012–2013 Neftechimik Nischnekamsk 2013–2016 Edmonton Oilers 2016–2017 St. Louis Blues 2017–2018 Color…
Нерчинський район рос. Нерчинский район Герб Нерчинського району Прапор Нерчинського району Основні дані Суб'єкт Російської Федерації: Забайкальський край Утворений: 1926 року Населення (2019): 27099 осіб Площа: 5435,26 км² Густота населення: 4,99 осіб/км² Населені пункти та пос
Goldregenpfeifer Goldregenpfeifer (Pluvialis apricaria) im Brutkleid Systematik Unterklasse: Neukiefervögel (Neognathae) Ordnung: Regenpfeiferartige (Charadriiformes) Familie: Regenpfeifer (Charadriidae) Unterfamilie: Pluvialinae Gattung: Pluvialis Art: Goldregenpfeifer Wissenschaftlicher Name Pluvialis apricaria (Linnaeus, 1758) Ein großer Schwarm Goldregenpfeifer.Ystad 2020. Ein männlicher Goldregenpfeifer während der Brutzeit, sein Bauch ist schwarz gefärbt und wird von einem weißen Str…
Komando Distrik Militer 1307/PosoLambang Kodim 1307/PosoNegara IndonesiaAliansiKorem 132/TDLCabangTNI Angkatan DaratTipe unitKodim Tipe BPeranSatuan TeritorialBagian dariKodam XIII/MerdekaMakodimBonesompe, Kabupaten PosoJulukanPakaroso Mosintuwu NapolantoPelindungTentara Nasional IndonesiaMotoBekerja dengan niat tulus dan ikhlasPertempuranOperasi TinombalaSitus webwww.kodim1307.idTokohDandimLetkol Inf Hasroel Tamin S.H., M.Hub.Int. Komando Distrik Militer 1307/Poso atau Kodim 1307/Poso, mer…
1995 single by Yōko Oginome Ashita wa Hareru!Single by Yōko OginomeLanguageJapaneseEnglish titleIt Will Be Fine Tomorrow!B-sideHeartbreakerReleasedAugust 23, 1995 (1995-08-23)Recorded1995GenreJ-popLength4:05LabelVictorSongwriter(s)Natsumi WatanabeTetsurō OdaYōko Oginome singles chronology Shiawase e no Jikan (1995) Ashita wa Hareru! (1995) Look Up to the Sky (1997) Ashita wa Hareru! (明日は晴れる!, lit. It Will Be Fine Tomorrow!) is the 35th single by Japanese singer Yō…
PinkPantheress discographyPinkPantheress in 2022Studio albums1Music videos8EPs1Singles15Mixtapes1Remix albums1 The discography of British pop singer PinkPantheress consists of one studio album, one mixtape, one extended play, and 15 singles. Albums Studio albums List of studio albums, with release date and label shown Title Details Peak chart positions UK[1] AUS[2] CAN[3] BEL(FL)[4] IRE[5] NZ[6] US[7] Heaven Knows Released: 10 November 2023…
لمعانٍ أخرى، طالع مجلس الشورى اليمني (توضيح). مجلس الشورى (1971-1975) مجلس الشورى النوع التأسيس 25 فبراير 1971 تاريخ الالغاء 29 أبريل 1975 النوع مجلس نواب منتخب القيادة رئيس مجلس الشورى عبد الله حسين الأحمر، لا يوجد حينها تعددية حزبية وسياسيةمنذ فبراير 1971 نائب رئيس المجلس الأول م…
Tipos de automóviles (Revista Madrid Automóvil, 1930) La clasificación de automóviles es un término general que se refiere a la manera de agrupar vehículos en categorías según sus características técnicas y comerciales. Un «automóvil de pasajeros» está pensado para el transporte privado de personas, aunque también se puedan cargar objetos grandes. Esta definición incluye los automóviles deportivos, todoterrenos, de turismo, monovolúmenes, los pickups y las furgonetas con varias…
Ernest Edgar KurthBorn(1895-11-01)1 November 1895Broken Hill, AustraliaDied4 January 1966(1966-01-04) (aged 70)Resting placeCornelian Bay, Tasmania Ernest Edgar Kurth, also known as E. E. Kurth, is best known for his work at the University of Tasmania with investigations into the chemical constitution and properties of Tasmanian and New South Wales oil shales, for which he was awarded the degree of Doctor of Science in 1934. During WWII he gave special attention to the pyrolysis of timber a…
1967 film by James Neilson The Adventures of Bullwhip GriffinTheatrical release posterDirected byJames NeilsonScreenplay byLowell S. HawleyBased onBy the Great Horn Spoon!by Sid FleischmanProduced byWalt Disney[1]StarringRoddy McDowallSuzanne PleshetteKarl MaldenCinematographyEdward ColmanEdited byMarsh HendryMusic bySongs:Richard M. ShermanRobert B. ShermanMel LevenGeorge Bruns Score:George BrunsProductioncompanyWalt Disney ProductionsDistributed byBuena Vista DistributionRelease date J…
As of February 2023[update], there were 7,150 electric vehicles registered in Louisiana.[1] Government policy As of May 2022[update], the state government offers tax rebates of up to $2,500 for electric vehicle purchases.[2] In June 2022, the state government introduced an annual registration fee of $110 for electric vehicles.[3] Charging stations As of May 2023[update], there were 191 public charging station locations with 488 charg…