霍尔婚姻定理：从礼物分配到组合数学的重要定理

霍尔婚姻定理：从礼物分配到组合数学的重要定理

霍尔婚姻定理（Hall's Marriage Theorem）是组合数学中的一个重要结果，它指出了从一组重叠的有限集合中选择不同元素的条件。这个定理不仅在数学领域有重要应用，还在计算机科学、经济学等多个领域有着广泛的应用。本文将从一个具体的礼物分配问题出发，逐步阐述霍尔婚姻定理的定义、应用及其证明。

问题引入

假设我有6份礼物（标记为1,2,3,4,5,6），需要在圣诞节分发给5位朋友（Alice、Bob、Charles、Dot、Edward）。我能否分配这些礼物，使得每个人都能得到他们想要的东西？

这显然取决于朋友们的喜好。如果他们都不喜欢任何礼物，那么我将无法完成分配。即使他们都喜欢某些礼物，我也可能无法满意地分配这些礼物。例如，如果没有人喜欢礼物5或6，那么我将只有4份礼物可以分发给5位朋友。或者假设：

• Alice想要：1,3
• Bob想要：2,4,5,6
• Charles想要：2,3
• Dot想要：1,2,3
• Edward想要：2

在这种情况下，仍然无法让每个人都满意。实际上，注意到我有四位朋友（Alice、Charles、Dot、Edward）只想要前三个礼物中的一个，这清楚地表明了问题的不可能性。

然而，霍尔婚姻定理指出，这是问题不可能的唯一方式。只要没有一个朋友子集喜欢的礼物数量少于该子集中的朋友数量，就总有一种方法可以让每个人都得到他们想要的东西。这就是霍尔婚姻定理的核心。

定理陈述

设(S)是一组有限集合。这里(S)可以是无限的，且(S)中的元素可以重复。(S)的横截集(T)是一个集合(T)和一个双射(f \colon T \to S)，使得(t \in f(t))对所有(t \in T)成立。

所以，横截集由(S)中每个集合的一个元素组成；重点是，即使集合重叠，所选的元素也必须是唯一的。当(S)是有限的时，(S)的横截集通常表示为(S)中集合元素的有序元组。

设(S = { {1,2,3},{2,3,4},{1,3} })。那么((1,4,3))是(S)的一个横截集：从第一个集合中选择1，从第二个集合中选择4，从第三个集合中选择3。注意，如果相反，我们尝试从第一个集合中选择1，从第二个集合中选择3，那么从第三个集合中选择任何元素都无法构成横截集。

（霍尔婚姻定理）设(S)是一组有限集合。假设对于(S)的每个子集(R)，集合的数量小于或等于这些集合中元素的总数：
[ |R| \le \left |\bigcup_{X \in R} X\right |. ]
那么(S)至少有一个横截集。

注：

1. 定理中给出的条件显然是横截集存在的必要条件，因为任何横截集都必须从(R)中的集合中包含( |R| )个不同的元素，所以这些集合必须一起包含至少( |R| )个元素。
2. 定理中给出的条件通常被称为"婚姻条件"。所以霍尔婚姻定理说，(S)有一个横截集当且仅当它满足婚姻条件。

应用到婚姻问题

假设有(n)个女人和(n)个男人，他们都想与异性结婚。假设每个女人有一份她愿意嫁的男人的名单，而每个男人愿意嫁给任何愿意嫁给他的人，且每个人只能有一个配偶。

在这种情况下，霍尔婚姻定理说，如果婚姻条件成立，即在任何一组女人中，这组女人中至少有一个女人愿意嫁的男人的总数大于或等于这组女人的数量，那么男人和女人可以全部配对结婚，使每个人都满意。

同样，这个条件显然是必要的。霍尔婚姻定理表明它也是充分的。要理解为什么定理在这种情况下适用，设(S_i)是第(i)个女人愿意嫁的男人的集合；那么上一段中提到的婚姻条件与集合族(S_i)上的婚姻条件相同。因此存在一个横截集(T)，这是一个对每个女人来说可接受的男人的选择。

二部图

霍尔婚姻定理可以用图论的语言重新表述。

一个二部图是一个图，其中顶点可以分为两个子集(V_1)和(V_2)，使得图中的所有边都连接(V_1)中的顶点和(V_2)中的顶点。（所以(V_1)或(V_2)中的顶点之间没有连接。）

一个图的匹配是一个没有公共顶点的边的选择。它覆盖一个顶点集(V)，如果(V)中的每个顶点都是匹配中某条边的端点。

匹配对应于邻接矩阵中1的选择，每行和每列最多有一个1。

假设一个二部图有部分(V_1)和(V_2)。霍尔婚姻定理说，存在一个覆盖(V_1)的匹配当且仅当对于(V_1)的每个子集(W)，在(W)中端点的边的数量(\ge |W|)。

其他应用

洗一副牌并将其分成13堆，每堆4张牌。证明总是有一种方法可以从每堆中选择一张牌，使得选择的13张牌包含每种牌面（一张A，一张K等）。

考虑由堆(i)中牌的牌面组成的集合族(S_i)。一个子族由(n)个子集组成，包含(4n)张牌的牌面。由于每种牌面只有4张，因此必须至少有(n)种不同的牌面。所以婚姻条件得到满足，因此存在一个横截集，这是问题所要求的。 (\square )

（Putnam 2012 B3）一个有(2n)支队伍的单循环赛持续了(2n-1)天，如下所述。在每一天，每支队伍与其他一支队伍进行一场比赛，每场比赛有一支队伍获胜，另一支队伍失败。在整个比赛中，每支队伍与其他每支队伍比赛一次。是否可以必然选择每天的一支获胜队伍，而不重复选择任何一支队伍？

答案是肯定的。在第(i)天，设(S_i)是获胜队伍的集合。每个集合(S_i)有(n)个元素。为了证明存在横截集，我们必须证明婚姻条件成立。

假设它不成立——即有(k)个集合(S_i)的并集包含少于(k)个元素；也就是说，假设在(k)天中有少于(k)支队伍至少赢过一次。在这种情况下，将至少有一支队伍在所有(k)轮中都输掉了比赛。但是，它输给了的(k)支队伍中至少有一支队伍赢过一次——矛盾。

所以存在一个横截集，这个横截集恰好是从每天选择一个不同的获胜队伍，如所要求的。 (\square)

其他例子可以在本页中找到：霍尔婚姻定理的应用。

定理证明

这里给出一个使用Dilworth定理的证明。假设( |S| = n )。设(S)中的集合为(X_1, X_2, \ldots, X_n)。设这些集合(X_i)的并集包含元素(x_1, x_2, \ldots, x_k)。现在在集合({ x_1, x_2, \ldots, x_k, X_1, X_2, \ldots, X_n })上定义一个偏序，使得(x_i \le X_j)当且仅当(x_i \in X_j)。（而且：任何两个(x_i)都不可比，任何两个(X_j)也不可比。）

婚姻条件意味着这个集合的最大反链是({x_1, x_2, \ldots, x_k })。这是因为如果存在一个更大的反链，包含(j)个(X)和(> k-j)个(x)，那么这些(j)个(X)将只包含不在反链中的(x)，其数量为(< j)，这将违反婚姻条件。

然后根据Dilworth定理，存在一个由(k)条链组成的覆盖。每个(x_i)恰好在一个链的覆盖中，且覆盖中的链要么是({x_i})，要么是({x_i,X_j})。由于每个(X_j)必须出现在链覆盖中，与(X_j)一起出现的(x_i)元素形成一个横截集。 (\square)