|
|
本帖最后由 hbghlyj 于 2022-3-25 21:46 编辑 Proofs from the book 第23章 有限集上的三个著名定理
在本章中我们考虑组合数学的一个基本主题:有限集$N=\{1,2,⋯,n\}$的一些子集组成的特定基族$\mathcal F$的性质和基数.我们从两个经典结果开始:
Sperner定理和Erdős-Ko-Rado定理.这两个结果的共同特点是它们都被证明了很多遍,还有它们各自开辟了组合集合论的一个新领域.看上去归纳法是证明这两个定理的自然途径.但我们此处要讨论的论证颇为不同而发人深思.
1928年,Emanuel Sperner提出并自己解决这样一个问题:给定集合$\mathcal N=\{1,2,\cdots,n\}$,称$N$的一些子集构成的集族$\mathcal F$为反链,若$\mathcal F$中没有哪个元素是$\mathcal F$中另一个元素的子集.反链最大可以是多少?很明显,所有的$k$-子集构成的族$\mathcal F_k$满足反链的要求,且$|\mathcal F_k|=\binom nk$.在二项式系数中找最大的(见第2章)可以得到大小为$\binom{n}{\lfloor n/2\rfloor}=\max_k\binom nk$的反链.Sperner定理则断言没有更大的了.
定理1. 一个$n$-集合的最大反链的基数是$\binom{n}{\lfloor n/2\rfloor}$.
证明. 诸多证明中,David Lubell的那个大概是最简短最优美的了.设$\mathcal F$是任意的一个反链,往证$|\mathcal F|\leqslant\binom{n}{\lfloor n/2\rfloor}$.证明的关键是考虑子集组成的链$\varnothing=C_{0} \subset C_{1} \subset C_{2} \subset \cdots \subset C_{n}=N$,且要求当$i=0,⋯,n$时,$|C_i|=i$有多少个链呢?显然,可以通过把$N$中的元素一个一个加上去来得到链,所以刚好有$N$的所有置换那么多个链,也就是$n!$.进一步,对$A\in\mathcal F$研究有多少个链包含$A$.这也容易:从$\varnothing$到$A$可以把$A$中的元素一个一个加上去,然后从$A$开始把剩下的元素一个一个加上去直到$N$.故若$A$含$k$个元素,则合起来就有$k!(n-k)!$个这样的链.注意不可能有链同时穿过$\mathcal F$中两个不同的元素$A$和$B$,因为$\mathcal F$是个反链.
为了完成定理的证明,令$m_k$表示$\mathcal F$中的$k$-子集数,则$|\mathcal F|=\sum_{k=0}^nm_k$.根据我们的讨论,穿过$\mathcal F$中某个元素的链的个数为$$\sum_{k=0}^{n} m_{k} k !(n-k) !$$而这个数不会超过所有链的数目$n!$.所以$$\sum_{k=0}^nm_k\frac{k!(n-k)!}{n!}\leqslant1\qquad\text或\qquad\sum_{k=0}^n\frac{m_k}{\binom nk}\leqslant1$$将分母换为最大的二项式系数,于是得到$$\frac1{\binom n{\lfloor n/2\rfloor}}\sum_{k=0}^nm_k\leqslant1,\qquad\text{亦即}\qquad|\mathcal F|=\sum_{k=0}^nm_k\leqslant\binom n{\lfloor n/2\rfloor}$$证毕.$\square$
检验: 当 $n$ 为偶数时所有的 $\frac{n}{2}$-子集构成的集族, 以及当 $n$ 为奇数时所有的$\frac{n-1}{2}$-子集构成的集族和所有的$\frac{n+1}{2}$-子集构成的集族确实是仅有的达到最大基数的反链!
我们的第二个结果则属于完全不同的性质.仍考虑集合$N=\{1,⋯,N\}$.称子集族$\mathcal F$为相交族,若$\mathcal F$中任两个元素至少有一个公共元.几乎可以马上发现最大的相交族的基数为$2^{n-1}$:若$A\in \mathcal F$,那么其补集$A^c=N∖A$与$A$相交为空,故不能出现在$\mathcal F$里.所以相交族最多可以有所有的子集数$2^n$的一半那么多的元素,即$|\mathcal F|\leqslant2^{n-1}$.另一方面,考虑含有某个固定点的所有子集,例如含有1的所有子集构成的族$\mathcal F_1$,则显然$|\mathcal F_1|=2^{n-1}$,问题就解决了.
现在问这么一个问题:若要求每个子集有同样的基数,比方说$k$,那么$\mathcal F$最大可能的基数是多少?称这样的族为相交$k$-集族.不妨设$n\geqslant2k$,否则任两个$k$-子集必相交,故无需证明.用上面的思想,取含固定点(如1)的所有$k$-子集当然可以得到满足条件的集族$\mathcal F_1$.显然$\mathcal F_1$里的子集可以通过把1加到$\{2,3,⋯,n\}$所有的$(k-1)$-子集里得到,因此$|\mathcal F_1|=\binom{n-1}{k-1}$.还可以更优吗?不──这就是Erdős-Ko-Rado定理.
定理2.当$n\geqslant2k$,一个$n$-集合的相交$k$-集族最大可能的基数是$\binom{n-1}{k-1}$.
1938年,Paul Erdős,柯召(Chao Ko)和Richard Rado发现了这个定理,但直到23年后才将之发表.此后众多证明和变形纷至沓来,但下面的由Gyula Katona给出的证明格外优雅.
证明.证明的关键是一个乍看上去和我们的问题毫不相干的简单引理.考虑被$n$个点分成$n$条边的圆周$C$,每条长为$k$的弧包含$k+1$个连续的点和它们之间的$k$条边.(见3#插图)
引理.设$n\geqslant2k$,且设有$t$条长为$k$的互异的弧$A_1,⋯,A_t$,使得任两条弧之交非空,则$t\leqslant k$.
为证引理,注意$C$的每一点至多是某1条弧的端点.事实上,若$A_i,A_j$有公共的端点$v$,则它们不得不向相反的方向延展(因为它们是相异的).但由$n\geqslant2k$它们将不会有公共边.固定$A_1$,由于每个$A_i(i\geqslant2)$与$A_1$有公共边,$A_i$的一个端点是$A_1$的内点.从上面看出这些端点各不相同,而$A_1$共有$k-1$个内点,所以$A_1$以外只能有至多$k-1$条弧,加起来至多有$k$条弧.引理得证.$\square$
现在继续证明Erdős-Ko-Rado定理.令$\mathcal F$是一个相交$k$-集族,考虑上述有$n$个点,$n$条边的圆周$C$.取环排列$\pi=(a_1,a_2,⋯,a_n)$,将$a_i$依顺时针写在$C$的各边上.对满足其$k$个元素连续地出现在$C$上的集合$A\in\mathcal F$计数.由于$\mathcal F$是相交族,引理告诉我们至多有$k$个这样的集合.这对所有的环排列都是如此,又因为一共有$(n-1)!$个环排列,故以上的方式产生了至多$k(n-1)!$个$\mathcal F$中的集合.其元素连续地出现在某个环排列上.对固定的集合$A\in\mathcal F$,我们计数了多少次呢?很容易:如果$A$的$k$个元素是按照某种顺序连续出现的,则$A$出现在$\pi$里.而我们共有$k!$种可能连续地书写$A$,以及$(n-k)!$种方式将剩余的元素排序.因此结论是固定的集合$A$恰好出现在$k!(n-k)!$个环排列里面,从而$$|\mathcal{F}| \leqslant \frac{k(n-1) !}{k !(n-k) !}=\frac{(n-1) !}{(k-1) !(n-1-(k-1)) !}=\left(\begin{array}{l}n-1 \\ k-1\end{array}\right)$$$\square$
我们仍可以问包含某个固定元素的$k$-集族是不是唯一达到最大基数的情形.当$n=2k$时这当然不对.例如,当$n=4$及$k=2$时(见3#插图),集族$\{1,2\},\{1,3\},\{2,3\}$的基数也是$\binom31=3$.一般地,当$n=2k$时,可以通过任意选取$k$-子集$A$与其补集$N∖A$这一对中的某一个来得到基数为$\frac12\binom nk=\binom{n-1}{k-1}$的最大相交$k$-集族.但当$n>2k$时,包含某个固定元素的特殊集族确实是唯一的情形了.读者请试着证明.
最后,我们转向第三个结果,这或许是有限集合论中最重要的基本定理了:Philip Hall在1935年证明的“婚姻定理”.它打开了今天所谓匹配定理的大门,且有广泛应用,其中的一些我们随后还会看到.
考察有限集$X$与$X$的子集$A_1,⋯,A_n$(不一定互异).称序列$x_1,⋯,x_n$为$\{A_1,\cdots,A_n\}$的一个相异代表系,若$x_i$两两互异,且对所有的$i$有$x_i\in A_i$.简称为SDR.
这样的一个系统当然未必存在,例如当某个集合$A_i$是空的.Hall定理的内容就是关于SDR存在的确切条件.
给出结果之前让我们从人的角度阐释一下,从中明白其俗称婚姻定理的缘由:考虑女孩的集合$\{1,⋯,n\}$与男孩的集合$X$.当$x\in A_i$,女孩$i$与男孩$x$有结婚的可能,即$A_i$是女孩$i$的所有可能对象的集合.存在SDR则表示存在每一个女孩都得以与自己喜欢的男孩结婚的集体婚配模式.
回到集合,我们的结果陈述如下:
定理3.令$A_1,⋯,A_n$为有限集$X$的一些子集.它们存在相异代表系当且仅当对每个$1\leqslant m\leqslant n$,任意$m$个子集$A_i$的并包含至少$m$个元素.
必要条件是显然的:若某$m$个集合$A_i$的并含有少于$m$个元素,则这$m$个集合就不能被互异的元素代表.令人惊讶的事实(导致了普适性的应用)是这个明显的条件也是充分的,Hall的原始证明相当复杂,随后出现了众多不同的证明,其中下面这个(属于Easterfield,被Halmos和Vaughan重新发现的)也许是最自然的.
证明. 对$n$归纳.当$n=1$时显然.令$n>1$,且设$\{A_1,⋯,A_n\}$满足定理的条件.该条件以下略为(H).对$1\leqslant\ell<n$,称$\ell$个集合$A_i$为临界族,若它们的并集的基数刚好为$\ell$.下面我们分两种情形讨论.
情形1.不存在临界族.
任取$x\in A_n$,从$X$中去掉$x$,考虑集合$A_1',⋯,A_{n-1}',$这里$A_i'=A_i∖\{x\}$.由于不存在临界族,任意$m$个集合$A_i'$的并仍包含至少$m$个元素.因此由归纳法知存在$\{A_1',⋯,A_{n-1}'\}$的SDR $x_1,⋯,x_{n-1}$.令$x_n=x$,合在一起就给出了原来集族的SDR.
情形2.存在临界族.
重新排序后可假定$\{A_1,⋯,A_\ell\}$是临界族,则有$\bigcup_{i=1}^\ell A_i=\tilde{X}$满足$|\tilde{X}|=\ell$.由$\ell<n$,应用归纳可得存在$A_1,⋯,A_\ell$的SDR.即存在$\tilde X$中的元素的排序$x_1,⋯,x_\ell$使得对所有的$i\leqslant\ell$,有$x_i\in A_i$.
考虑剩下的集合$A_{\ell+1},⋯,A_n$,任取它们中的$m$个.根据条件(H),$A_1,⋯,A_\ell$和这$m$个集合的并包含至少$\ell+m$个元素,所以这$m$个集合在$\tilde X$之外还包含至少$m$个元素.换言之,集族$$A_{\ell+1} \backslash \tilde{X}, \cdots, A_{n} \backslash \tilde{X}$$也满足条件(H).归纳假设给出$A_{\ell+1},⋯,A_n$的在$\tilde X$之外的一个SDR.将其与$x_1,⋯,x_\ell$合在一起,我们得到所有集合$A_i$的一个SDR.证毕.$\square$
正如我们提到过的,Hall的定理是如今已很宏大的匹配理论领域的开端.在诸多变形和分枝中让我们提一个特别有意思的结果.我们请读者来自行证明:设集合$A_1,⋯,A_n$的集数都是$k\geqslant1$,并且没有元素含在多于$k$个集合里,则 存在$k$个SDR使得对任意的$i$,$A_i$的$k$个代表元是互异的,从而合在一起构成$A_i$. |
|
