04 偏序集

偏序集的定义

我们要讨论偏序集，与它对应的是我们熟悉的“全序集”。比如，实数就是一个全序集，给定任意两个实数$a,b$，那么“$a \leq b$”和“$b \geq a$”中总有一个是成立的，所以这种“序结构是完全的”，任何两个元素都可以“比较大小”。而对于偏序集来说，这却是不一定的。我们定义的一种比较方法可能并不能对任何两个元素适用。比如我们可以把集合间的包含关系看作一种序结构，如果一个集合$S \subseteq T$，我们就说$S \leq T$。而对于两个有交集却不包含的集合，就无法比较大小。由此可见，偏序集比全序集更广泛，全序集是一种特殊的偏序集。

严格来说，一个偏序集是集合$P$和比较关系$\leq$组成的二元组$(P,\leq)$。这个二元组是偏序集当且仅当满足三个性质：自反性（$a \leq a$），反对称性（$a \leq b \ \land \ b \leq a \Rightarrow a=b$），传递性（$a \leq b \ \land \ b \leq c \Rightarrow a\leq c$）。如果$a \leq b$且$a \neq b$，我们就说$a < b$。

在偏序集中，极值和最值是完全不同的概念。如果一个元素没有任何比它大的元素，它就是极大值；而一个元素要是最大值，它必须比其他所有元素都要大。后者一般是很难做到的，因为那样就要求这个最大元素要能和所有元素作比较。作比较这一做法在偏序集中本身就是不一定能完成的事。

我们可以用Hasse图来表示一个偏序集。Hasse图是一个DAG，两个元素$a,b$间有$a$到$b$的边当且仅当$a<b$，同时不存在任何元素$c$夹在他们中间使得$a<c<b$。

整数的整除关系$(\Z,|)$也是一个偏序集。可以对他们验证上面三条性质。同时，刚才已经举例说明了$(2^U,\subseteq)$是一个偏序集（$2^U$代表$U$的所有子集构成的集合）。我们能够发现，集合的包含关系是一种最一般的偏序关系（仅讨论有限的偏序集），任何一个偏序集我们都可以同构地构造一个子集关系——只需在Hasse图上把所有子节点元素都加入到父节点的元素集合上，这样父节点就一定包含子节点了。如果按照元素个数来给Hasse图分层，那么最底下的源点就是空集，最上面的汇点就是全集。

偏序集中的链

如果在偏序集中选出一个两两可比较的元素集合（全序集），那么这个集合一定能在Hasse图上被表示成一条链（或者几条，因为他们不一定是连续的，但它们一定能看成某条更长的链的一部分），我们称它为偏序集的一个链。

我们说一条链是极大的，当且仅当增添任何一个其他元素它都不再是链。而最大（最长）的链指的是拥有元素最多的链。偏序集的高度定义为最大链的长度（元素个数）。

我们还可以定义“反链”，它是任意两个元素都不能互相比较的一个元素集合。对于反链，我们也用同样的方法定义极大和最大。其中，最大反链的长度称为偏序集的宽度。

链划分

如果我们找到若干条互不相交的链，它们恰好覆盖了所有元素，那么就称这是一个“链划分”。同理，也可以定义反链划分。一个划分的大小就是这个划分包含的链的个数。

关于链划分和反链划分，有两个对偶的定理：

对于任何偏序集，最小反链划分的大小等于最长链的大小（高度）。设最长链大小为$h$，如果存在一个小于$h$的最小反链划分，那么最长链上至少有两个点属于同一个反链，而最长链上的任意两点都是可以比较大小的，因此矛盾。所以最小反链划分一定大于等于$h$。那么只需构造一个长度为$h$的反链划分。我们对$h$归纳。当$h=1$时，元素集合本身就构成了反链划分，显然成立。假设对于任何高度小于$h$的偏序集这个定理都已经成立，那么对于高度为$h$的偏序集，它有若干条长度为$h$的链。对于每个长度为$h$的链，我们取最顶端（Hasse图上）元素。所有这些被取出的元素之间一定两两不可比较，否则我们就能构造出一条长度为$h+1$的链，矛盾。因此这些元素构成了一条反链。把这些元素从原图上删掉之后，原图的高度一定小于$h$，否则就存在一条长度为$h$的链，添加上删掉的元素就会形成长度为$h+1$的链，矛盾。因此删点后的原图的最小反链划分为$h-1$，加上删掉的点构成的反链，我们就构造出了一个大小为$h$的反链划分。证毕。

对于任何偏序集，最小链划分的大小等于最长反链的大小（宽度）。设最长反链大小为$w$，如果存在一个小于$w$的最小链划分，那么最长反链上至少有两个点属于同一个链，矛盾。所以我们只需要构造一个长度为$w$的最小链划分。现在，我们对偏序集的元素个数来归纳地证明最小链划分的大小等于最长反链的大小。当$|P|=1$时，宽度为1，最小链划分为1，成立。假设对于任何元素个数小于$|P|$的偏序集这个定理已经成立。我们找出$P$的一条最长链并把它删除，得到偏序集$P'$。$P'$的宽度不可能变得更大（不然$P$中也会有更长的最长反链），因此$P'$宽度要么更小要么相同。对$P'$可以用归纳假设。如果宽度变小，那么$P'$有大小不超过$w-1$的最小链划分，加上这条最长链就构造出了不超过$w$的划分。如果宽度不变，那我们在$P'$中依然可以找出一个长度为$w$的反链，这些元素记为集合$A$。我们把$P$中所有能够大于$A$中某个元素的元素收集起来构成集合$U_A$，所有能够小于$A$中某个元素的元素收集起来构成集合$D_A$（都是在原来的偏序集里讨论）。这三个集合一定覆盖了$P$中所有元素（如果没有覆盖，那么存在某个元素又不能大于$A$中某个元素也不能小于$A$中某个元素也不属于$A$，因此可以把这个元素加入$A$，这就与$P$的宽度为$w$矛盾），并且互相没有交集。由于$A$是在删除最长链的情况下找出来的，因此当我们把最长链加回来的时候，最长链上的元素一定在$U_A$或$D_A$里。考虑最长链上最大的元素$x^+$，它要么在$U_A$里要么在$D_A$里，如果它在$D_A$里，那么链上的元素全都小于$A$中某个元素，把这个元素加进链上就会形成更长的链，矛盾，因此$x^+$一定在$U_A$里；同理，最长链上最小的元素$x^-$一定在$D_A$里，这就证明了$U_A$和$D_A$非空，所以$|U_A \cup A|<|P|$，可以用归纳假设，找出$w$条链覆盖它；同样地，可以找出$w$条链覆盖$|D_A \cup A|$。由于$A$是反链，这$w$条链（两边都是）都是独立的以$A$中一个元素为顶端或末尾的，所以把这两部分链合并起来就一定能得到$w$条链，它覆盖了所有元素。这个定理称为Dilworth定理。

Min-Max定理

像Dilworth定理这样最小的什么等于最长的什么这样的定理称为Min-Max定理，这种定理出现在数学的很多领域，它们往往是某种对偶定理的具体表现形式。

Hall婚姻定理就是一个Min-Max定理（抽象了的）：一个两边各$n$个节点的二分图中，记左侧节点集合$S$的函数$N(S)$表示右侧节点中与$S$中节点有边相连的点的集合，该二分图存在完美匹配当且仅当对任何$S$恒有$|N(S)| \geq |S|$。“$\Rightarrow$”很容易，如果有完美匹配，那么作为任何$S$的匹配的点的集合就已经有$|S|$个，因此显然有$|N(S)| \geq |S|$。对于“$\Leftarrow$”，我们用偏序集的Dilworth定理来证明。把二分图左侧和右侧的点都看作偏序集里的元素，二分图的边$(l_i,r_j)$就定义为偏序关系$l_i \leq r_j$。我们发现，如果我们给边都带上从左到右的方向，二分图本身就形成了偏序集的Hasse图。那么，单侧的节点就可以构成一个反链，所以最长反链至少为$n$。有没有可能大于$n$？如果存在，那么它一定同时动用了左侧和右侧的节点。那么设左侧用到的点集为$L$，右侧用到的点集为$R$。那么对应的$|N(L)| \geq |L|$。由于$L \cup R$形成了反链，所以$N(L)$与$R$一定是无交的，因此$|N(L) \cup R| \geq |L|+|R|>n$，这与右侧只有$n$个节点矛盾。因此，这个偏序集的最长反链就是$n$！根据Dilworth定理，其最小链划分也是$n$。在这里，每条链就是二分图的一条边，这些没有公共点（因为分划要求没有交集），所以二分图一定有完美匹配。

推论：用类似的方法可以证明，如果把条件改为左侧节点个数$|L|$小于右侧节点个数$|R|$，可以由$|N(S)| \geq |S|$恒成立推出存在一个大小为$|L|$的匹配。

接下来我们用Hall婚姻定理证明Kőnig定理：二分图的最大匹配等于最小点覆盖（一个点覆盖是原图的一个点集，要求每条边至少有一个点在这个点集里，换言之这个点集“覆盖”到了所有边）。假设二分图有一个大小为$k$的匹配，那么这些匹配边是互相独立的，想要覆盖这些边就已经至少需要$k$个节点，因此原图的点覆盖至少大于等于$k$。也就是说，最大的匹配也不可能比某个点覆盖的大小还大。匹配大小本身就是被点覆盖给bounded的了。当我们取出一个最小的点覆盖，就知道所有可能的最大匹配都不可能超过这个最小点覆盖。于是我们只需证明存在一个与最小点覆盖大小相同的匹配！我们设最小点覆盖为$A \cup D$，其中点集$A$在左侧，点集$D$在右侧，设$A$中的子集$S$，与$S$的点相连的边形成集合$E_1$，与$A \cup D$中其余的点相连的边形成$E_2$，$E_1 \cup E_2$覆盖了所有边。如果把$S$全部换成$N(S)$，那么$E_1$依然被$N(S)$完全覆盖，同时$E_2$也依然被覆盖。所以$N(S) \cup D$也是一个点覆盖，同时我们依然能控制所有的边。我们取$N(S)$中与$D$没有交集的那部分，构成集合$F$，那么$F \cup D$也是一个点覆盖。因为$A \cup D$是最小的，所以有$|F|+|D| \geq |A|+|D|$，即$|F| \geq |A|$，因此$|F| \geq |A| \geq |S|$。设二分图左边的点集去掉$A$以后为$B$，右边的点集去掉$D$以后是$C$，那么在子图$A \cup C$中，它满足$|N(S)| \geq |S|$恒成立的条件，根据Dilworth定理的推论，可以推出$A \cup C$中存在大小为$|A|$的匹配（$|C|$一定大于等于$|A|$，因为$|C| \geq |N(A)| \geq |A|$）。对称地，我们在$D$中选子集重复一遍刚才的证明，可以推出在$B \cup D$中存在一个大小为$|D|$的匹配。由于$A \cup C$与$B \cup D$无交，我们就在原图找到了一个$|A|+|D|$的匹配——一个大小和最小点覆盖相等的匹配！

现在我们用Kőnig定理反过来证明Dilworth定理。我们可以把一个偏序集构造成一个二分图，设偏序集大小为$n$，那么我们就构造左右各$n$个节点的二分图，如果有偏序关系$i \leq j$，就让左侧的第$i$个点与右侧的第$j$个点之间连一条边。现在假设这个二分图有一个任意的匹配$M$，我们可以根据这个匹配来构造一个偏序集上的链划分：把匹配上的边对应回偏序集上，已经形成了若干条链了，剩下的节点加入没有在匹配中覆盖，可以一个节点孤立地自成一条链。总之，我们能构造出一个$m$条链的链分划。容易计算得到，由于$m$条链覆盖了$n$个点，因此链分划里的边的总数就是$n-m$。（$n$个点，$m$棵树，一共$n-m$条边）而这个匹配的大小$|M|$恰好就是链分划中的边数，因此有$n-m=|M|$。同时，我们可以根据这个二分图的任意一个点覆盖$S$构造偏序集中的一条反链。点覆盖不一定触碰到了所有$1$到$n$中的节点（左边也没碰到，右边也没碰到），所有这样的节点形成的集合在二分图里是相互没有边的，不然这条边就没有被点覆盖覆盖了。因此这些节点在偏序集里就对应着一条反链。设刚才的点覆盖在偏序集里触碰到的节点个数为$T$，那么反链的长度$A$就是$n-T$。现在，我们选择最大匹配$M'$和最小点覆盖$S'$。根据Kőnig定理，$|M'|=|S'|$。最小点覆盖触碰到的节点个数$T'$一定满足$T' \leq |S'|$，因此此时的反链的长度$A'=n-T' \geq n-|S'|=n-|M'|=m$。其中$m$是最大匹配对应的链分划的大小。因此我们证明了，存在一条反链，其长度大于等于链分划的大小。而再一次，如果反链长度大于某个链分划的大小，那么反链上一定有两个点落在同一条链中，矛盾。因此最长的反链的长度也一定小于等于最小的链分划大小。而我们找到了一条长度大于等于某个链分划的反链，它的长度一定大于等于最小链分划的大小。所以，它就是最长反链，并且它的大小必须等于最小链划分的大小。这正是Dilworth定理！

这样，我们就证明了Dilworth定理、Hall婚姻定理、Kőnig定理全都是等价的！

Sperner定理

任何一个偏序关系都可以“看作”是集合的包含关系，但是这些集合并不一定构成了某个全集的所有可能子集。现在我们就特别地来关注一个集合所有子集间以包含关系为偏序的偏序集，即考虑$P=(2^{[n]}, \subseteq)$这个偏序集。我们有结论，这个偏序集的宽度（最长反链大小）一定是$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$。这个定理叫做Sperner定理。

如今偏序集的一个节点是$\{1,\cdots,n\}$的一个子集。一条反链就是一系列互相不包含的子集。如果这些子集的大小相同，那么它们之间一定无法相互包含。那么假如规定子集的大小都为$k$，就可以构造一个大小为$\dbinom{n}{k}$的反链。那么根据组合数的单调性，这个值最大可以达到$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$。也就是说我们已经找到了Sperner定理中要求的反链了，我们只需要证明所有反链（最长反链）都不可能长度超过它。假设这个偏序集的一个最长反链为$S_1,\cdots,S_w$。那么我们记$C_i$表示所有包含$S_i$的极大链的集合。由于我们偏序的元素是所有子集，在Hasse图上任何一个经过$S_i$的极大链都向上抵达了$[n]$向下抵达了$\empty$，即每条极大链长度都是$n+1$（否则一定可以加上漏掉的集合形成更大的链，与极大矛盾）。因此容易写出$|C_i|=(n-|S_i|)!|S_i|!$。并且容易观察到，$C_1$到$C_w$就一定无交，因此$\sum\limits_{i=1}^{w}|C_i|$一定小于等于所有长度为$n+1$的链的总数（共$n!$条），于是$n! \geq \sum\limits_{i=1}^{w}(n-|S_i|)!|S_i|!$，这个结构和组合数非常类似，因此我们配凑出$1 \geq \sum\limits_{i=1}^{w}\dfrac{(n-|S_i|)!|S_i|!}{n!}=\sum\limits_{i=1}^{w}\dfrac{1}{\binom{n}{|S_i|}}$，把所有$\dbinom{n}{|S_i|}$都放缩为$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$，就有$1 \geq \sum\limits_{i=1}^{w}\dfrac{1}{\binom{n}{|S_i|}} \geq \sum\limits_{i=1}^{w}\dfrac{1}{\binom{n}{\lfloor\frac{n}{2}\rfloor}}=\dfrac{w}{\binom{n}{\lfloor\frac{n}{2}\rfloor}}$，于是证明了$w \leq \dbinom{n}{\lfloor\frac{n}{2}\rfloor}$，即最长反链长度不超过$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$。因此偏序集的宽度就必须是$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$。

我们尝试用Sperner定理来证明一个“Erdős定理”：给定$n$个大于等于1的实数$x_i$，把它们累加时每个$x_i$都可以取正或取负，这样得到$2^n$个结果$S(N)$（$N$可以理解为取正数的下标集合），那么任取一个实数轴上长度为$2$的开区间，最多只有$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$个结果落在这个开区间里。

每一个结果都可以理解为是由$N$的选取决定的，因此整个结果可以看作是关于$N$的包含关系的偏序集。对于互相包含的两个偏序集中的元素，它们的结果之差的绝对值就是若干$2x_j$的和。因为$x_j \geq 1$，所以任意两个在偏序集中能比较大小的元素其结果之差$\geq 2$，因此它们一定不能落在同一个开区间里，所以能落在开区间里的元素一定不能互相比较大小，所以它们对应偏序集上的一条反链。而我们的偏序集恰恰是一个完全的子集集合，所以根据Sperner定理最长反链就是$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$，因此能落在同一个开区间里的元素个数最多就是$\dbinom{n}{\lfloor\frac{n}{2}\rfloor}$。