Hall’s marriage theorem
Peter J. Cameron · 2025
Read Hall’s marriage theorem by Peter J. Cameron (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23159.txt.
Introduction
Peter Cameron, writing alone in 2025, tells the tale of Hall's marriage theorem and its wide wake. The 1935 claim is spare. A set of sets can pick one unlike rep from each if and just if each sub-clan holds at least its own count of parts in its join. Hall's short proof is set out in full.
Kin claims that came first, some the same and some more strong, get their due. Then the walk turns to the turns the claim has steered: match craft, flow, codes, and fields far from its birth. Few short claims have fed so many trades. The piece is both proof and map, for hands new to the claim and for those who owe it a tool.
Catalog record
| CREATOR | Peter J. Cameron |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23159
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hall’s marriage theorem Peter J. Cameron Abstract In 1935, Philip Hall published what is often referred to as “Hall’s marriage theorem” in a short paper (P. Hall, On Representatives of Subsets, J. Lond. Math. Soc. (1) 10 (1935), no.1, 26–30.) This paper has been very influential. I state the theorem and outline Hall’s proof, together with some equivalent (or stronger) earlier results, and proceed to discuss some the many directions in combinatorics and beyond which this theorem has influenced. MSC: Primary 05D15; secondary 05A16, 05B15, 05C70 1 Introduction According to the zbMath database, Philip Hall wrote only 53 papers, a relatively small number, 48 of which were single-authored. His name is known to generations of group theorists because of his profound contributions to the subject. But his most cited paper, with nearly twice as many citations as the Hall–Higman paper in second place [ 18 ] , is the one in which he proved what is now called Hall’s marriage theorem [ 17 ] . It is titled “On representatives of subsets”, and is four and a half pages long. The application which Hall may have had in mind is the fact that, if G is a group and H a subgroup of finite index n , then there are n elements g_{1},\ldots,g_{n}\in G which are simultaneously left and right coset representatives of H in G . However, John Britnell informs me that he and Mark Wildon searched Hall’s published work and found no evidence that he ever used this result. Indeed, the result had been published by G. A. Miller in 1910 [ 22 ] . Before stating the theorem, I give one definition, with a comment. Let (T_{1},\ldots,T_{n}) be an n -tuple of subsets of a finite set S . A system of distinct representatives or SDR for the n -tuple is an n -tuple (a_{1},\ldots,a_{n}) of elements of S such that a_{i}\in T_{i} for all i , and a_{i}\neq a_{j} for i\neq j . (Hall calls this a complete set of distinct representatives, or CDR; to avoid confusion I have used the current term.) Also, the set \{a_{1},\ldots,a_{n}\} is called a transversal to the family. Hall’s Theorem states: Theorem 1.1 A necessary and sufficient condition for the existence of an SDR for a tuple (T_{1},\ldots,T_{n}) of sets is that, for 0\leq k\leq n , any k of the sets contain between them at least k elements of S . Proof The necessity of the condition is clear. I sketch Hall’s proof of the sufficiency. It depends on a lemma asserting that, with the hypotheses of the theorem, if (a_{1},\ldots,a_{n}) is an SDR and P=\{i:1\leq i\leq n,a_{i}\hbox{ lies in every SDR}\}, then the union of the sets T_{i} for i\in P is \{a_{i}:i\in P\} . Given this, the proof is by induction on n . The induction clearly starts at n=1 . Suppose that the hypotheses of the theorem hold, and that the theorem is true for n-1 sets. By induction, there is an SDR (a_{1},\ldots,a_{n-1}) for (T_{1},\ldots,T_{n-1}) . Thus, the theorem will hold unless T_{n} is contained in every SDR for (T_{1},\ldots,T_{n-1}) . Let P^{*}=\{i:1\leq i\leq n-1,a_{i}\hbox{ lies in every SDR for }(T_{1},\ldots,T_{n-1})\}, and R^{*}=\{a_{i}:i\in P^{*}\} . If T_{n}\subseteq R^{*} , then the sets T_{i} for i\in P^{*} or i=n are |P^{*}|+1 in number but by the lemma contain only |P^{*}| elements among them, contrary to hypothesis. To deduce the result about cosets, we let H be a subgroup of G of index n . Since the intersection of the conjugates of H is a normal subgroup of finite index in G , by taking the quotient we may assume that G is finite. Let L_{1},\ldots,L_{n} be the left cosets and R_{1},\ldots,R_{n} the right cosets of H in G ; for i=1,\ldots,n , let T_{i}=\{j:L_{i}\cap R_{j}\neq\emptyset\}. The union of k left cosets contains k|H| elements, and so cannot be contained in fewer than k right cosets. So the union of k of the sets T_{i} has cardinality at least k , and Hall’s theorem gives a SDR (a_{1},\ldots,a_{n}) . Choosing g_{i}\in L_{i}\cap R_{a_{i}} for i=1,\ldots,n gives the required coset representatives. The name “Hall’s marriage theorem” comes from the following interpretation. Let \{b_{1},\ldots,b_{n}\} be a set of boys, and S a set of girls; let A_{i} be the set of girls who know b_{i} . Then a necessary and sufficient condition for it to be possible to marry each boy to a girl he knows is that any k boys know between them at least k girls, for all k . 2 Precursors and equivalents In fact, other mathematicians stated equivalent results before Hall. What follows is a very brief account; Hall’s version became the most influential, but I leave to a more detailed historical analysis the question of why this happened. However, the legacy of this activity is shown by the wide variety of proofs of the theorem which appear in textbooks and expository accounts. First, after some definitions, I state some results which are in a sense equivalent to Hall’s theorem. A bipartition of a graph is a partition of the vertex set into two parts such that each edge is incident with one vertex in each part; a graph is bipartite if it has a bipartition. A matching is a set of pairwise disjoint edges; it is perfect if every vertex is incident with an edge of the matching. A set of vertices is independent if it contains no edge. A vertex cover is a set of vertices meeting every edge. Theorem 2.1 (i) Let G be a graph with bipartition \{A,B\} . Suppose that, for every subset X of A , there are at least |X| vertices in B which have a neighbour in A . Then G has a matching which covers every vertex in A . (ii) Let M be an n\times m matrix. A necessary and sufficient condition for the existence of an injective map f from \{1,\ldots,n\} to \{1,\ldots,m\} such that M_{i,f(i)}\neq 0 for all i is that any k rows together have non-zero elements in at least k columns, for 0\leq k\leq n . (iii) Let (T_{1},\ldots,T_{n}) be a family of subsets of S . Suppose that there is a positive integer d such that, for 1\leq k\leq n , any k sets from the family contain between them at least k-d elements. Then there is a partial SDR of size n-d ; that is, elements a_{i_{1}},\ldots,a_{i_{n-d}} in S such that a_{j}\in T_{j} for j\in\{i_{1},\ldots,i_{n-d}\} and a_{j}\neq a_{k} for j\neq k . Proof Parts (i) and (ii) are relatively straightforward variants of Hall’s theorem. For (i), for each a\in A , let T_{a} be the set of its neighbours in B ; the hypotheses in the graph imply Hall’s hypotheses, and the conclusion is then equivalent to Hall’s. For (ii), for each row index i of the matrix, we take T_{i} to be the set of columns in which the i th row has non-zero entries. Part (iii) is the defect form of Hall’s theorem. Though apparently more general, it is easily proved from the original form, as follows. Take a set D of d “dummy” elements not lying in any of the sets T_{i} , and let T_{i}^{*}=T_{i}\cup