动机
在固定基础集的所有子集中,若要求所选子集两两互不包含,最多能选出多少个?选取全部相同大小的子集显然可行。中间大小的子集最多,这暗示存在一个最优答案,但混合不同大小的子集是否不可能做得更好,并不显然。
Dilworth 定理把反链的大小与某个划分的最优值等同起来,但它本身并不能算出子集偏序集的宽度。这里我们利用子集所具有的额外对称性:每个排列都生成一条由嵌套子集构成的完整链。统计某个被选中的子集落在多少条这样的链上,会对小集合与大集合赋予不同的权重。这种加权计数既证明了极值上界,也给出了对含有多个秩的集族的有用限制。
定义
定义 6.3.1
(布尔层与反链集族)
对 ,记 ,并以包含关系为 赋予偏序。其第 层 由所有 元子集组成,故 。若集族 中任意两个不同成员互不包含,则称 为反链。定义它的 Lubell 权重为
每个分母中的二项式系数都是正数。当 时,基础集为空,布尔(Boole)偏序集只有一个元素,即空子集。
布尔偏序集中的一条极大链恰含每个大小从零到 的子集各一个。它由每一步添加一个新的基础集元素得到,所以这样的链恰有 条。这里“极大”指它在该偏序集内不能再被延长;布尔偏序集的极大链都具有最大可能的大小 。在一般的偏序集中,这两种含义不必一致。
定义 6.3.2
(一层的上影)
对 与 ,其上影为
它记录了在反链中选取 的某个成员之后,下一层中被禁止选取的所有集合。多个成员可能禁止同一个下一层集合,因此关联次数不能当作互不相同的上影成员来计数。
定理/命题
定理 6.3.3
(LYM 不等式)
对每个反链 ,
不要求集族限于单独一层。空集族的权重为零。
定理 6.3.4
(Sperner 的最优上界与取等情形)
中的每个反链的大小至多为 。完整的中间层可达到该上界。若 为偶数,则这是唯一的最大反链;若 为奇数,则仅有的最大反链是两个完整的中间层。
定理 6.3.5
(归一化的上影不等式)
对 与 ,
该不等式比较的是相邻两层中所占的比例,并不是说它们的原始基数总是按同一方向排序。
证明思路或证明
证明
(在极大链上计数成员)
统计由 的成员 与包含它的极大链所组成的对。若 ,则生成该链的排列必须先把 的元素放在前面(顺序任意),再把其余元素放在后面(顺序任意),共有 种选择。另一方面,每条极大链至多包含反链的一个成员。因此
两边除以 即得 LYM 不等式,其中包括大小为零与大小为 的端点情形。
证明
(双重计数直接包含关系)
对于上影不等式,统计满足 、 且 的对 。每个被选中的 元集恰有 个直接上集,而每个上影成员至多包含 个被选中的 元集。因此
再利用 ,即得归一化形式。
证明
(由权重上界到最优上界及其取等情形)
二项式系数之比 表明,最大的层大小为 :当 为偶数时取在一个中间秩,当 为奇数时取在两个中间秩。因此任何反链的每个成员对其权重的贡献至少为 。于是 ,这就证明了大小上界。每个中间层本身是反链,所以该上界可以取到。
若等号成立,则每个成员都必须位于最大的层上,因为位于较小层的成员的贡献严格大于 。当 为偶数时,只有一个秩的大小为 ,所以该集族必为整个中间层。这也涵盖了 的情形。
当 为奇数时,考虑 与 之间的二部包含图。两部分的大小都是 ,且每个顶点的度数都是 。该图是连通的:任意两个 元集可以这样连接起来——反复把一个不在目标集中的元素替换为目标集中缺少的元素,每次替换都经过二者共同的 元并集。每个上层顶点都有下层邻点,所以这些路径连通了整个图。当 时,该图就是一条边。
它的下半部分的每个非空真子集 ,其邻点个数严格多于 自身的大小。先由边的计数得到邻点个数至少与之相等。若两者相等,则邻点集上的每条边都已来自 ,而 上的每条边又都留在该邻点集之内,它们就构成一个完整的连通分支,与图的连通性矛盾。现在,一个最大反链由下部分 和避开其上影的上部分组成,其大小至多为
非空真子集的下部分会使这个值小于 。因此下部分必须为空,或者是整个下层;要达到 ,另一部分也相应地被确定。这就证明了奇数情形的取等分类。
证明透视
不可比性、单峰性与连通性在哪里进入
三个事实各有分工。链计数给每个秩为 的成员代价 ;反链假设恰好只使用一次:没有极大链同时经过两个成员。关于集族的其他性质一概没有用到。二项式系数的单峰性把代价转化为大小:每个代价至少为 ,所以 。取等迫使每个不等式都取等号,从而把每个成员固定在大小为 的层上; 为偶数时论证到此结束。 为奇数时两层并列,需要另一个想法:大小为 的混合集族需要一个非空真子集 使 。包含图两边度数都是 的正则性只给出 ;排除混合集族所需的严格不等式来自连通性。
例题详解
例题 6.3.6
(六个二元子集构成四元集上的最大集族)
的六个二元子集构成一个反链。每个的权重为 ,总和为一。极大链共有 条,每个二元子集属于其中 条。这六组关联恰好覆盖全部 条链,每条链各含唯一的一个二元成员。Sperner 定理证明不存在更大的反链;偶数情形的取等结论说明,这个完整的层是唯一大小为六的集族。
例题 6.3.7
(可行的权重预算未必能实现给定的秩分布)
在 上,设反链含有四个单元素集与 个二元子集。LYM 给出 ,故 。但实际的包含限制更强。重新标号后,这四个单元素集为 。任何二元子集都必须避开这四个元素,而只剩下元素五,这是不可能的。因此 。权重不等式只是必要条件,并不是对每个给定的秩分布都能据以构造的充分规则。
例题 6.3.8
(上影解释了混合中间各秩时的损失)
在 上,设 为含有元素一的四个二元子集。它的上影是含有一的六个三元子集。两个中间层都有十个元素,所以归一化后的大小分别为 与 。二元成员恰为这四个二元子集的反链至多能再加入上影之外的四个三元子集,因而大小至多为八。通过混合这些选择,无法达到最优值十。从被选中的二元子集出发的关联数为十二;每个上影三元子集包含其中两个,这就解释了实际上影成员为六个。
同一证明的期望形式
取一个均匀随机的排列,并列出它的各个前缀子集。对于固定的子集,同一秩的所有集合作为前缀集出现的可能性相同。因此它出现的概率是该层大小的倒数。令一个随机变量统计该链所遇到的所选集族的成员个数。它的期望值是这些出现概率之和,恰好就是 Lubell 权重。
对于反链,该变量始终至多为一,所以其期望至多为一。这与前面是同一个有限计数证明,只是用概率的语言表达,并不是对集族另作随机输入的假设。各个出现事件不必相互独立。事实上,两个不同的反链成员不可能同时出现在一条链上,正是这种依赖性使上界成立。
这一观点有助于理解权重。小的子集落在所有极大链中相对较大的一部分上,因为它所在的层选择很少。因此它比位于宽阔中间层的子集消耗更多的链预算。最优化比较的正是这些代价,而不是假设每个集合使用相同的资源。
上影的增长能说明什么,不能说明什么
归一化不等式说明,当一个层上的集族被换成它的整个上影时,所占的比例不会下降。集合的个数是否增加,则取决于两层的相对大小。在中间层以下,下一层至少一样大,所以上影的基数至少与原来相同。在中间层以上,较小的下一层可能含有更少的集合,即使它占该层的比例变大。
例如,取三元基础集的全部三个二元子集。它们的上影只是整个三元集。基数从三降为一,而两个归一化比例都等于一。丢掉分母,就会把正确的归一化命题变成错误的、关于基数的普遍性断言。
证明先按重数统计关联,再对互不相同的邻点个数进行估计。关联上界中取等,要求每个上影成员都含有尽可能多的被选中前驱。在奇数维布尔偏序集并列的中间层上,连通性使这一点极其苛刻。正是这一额外限制,使混合的集族无法悄悄地达到与完整一层相同的极值大小。
概念视角组合
对极大链的覆盖,而不是格的图示
被选中的子集占据经过它的每一条极大链。不同的反链成员占据互不相交的链集合,所以它们归一化后的占有量之和至多为整个链集合。这一解释依赖于全部极大链及其精确个数;一幅小的 Hasse 图中可见路径的条数并不是所要求的样本空间。
究竟解决了哪个极值问题?
Sperner 定理计算的是布尔偏序集的宽度。随后 Dilworth 定理保证它的全部子集可以划分为同样数目的链。LYM 证明中使用的极大链一般并不是这样的划分:它们大量重叠,只是作为一个对称的检验链族来计数。混淆链的这两种用途,会使论证声称得到了一个它从未构造过的不交分解。
常见错误
(包含意义下极大不等于最大)
证明所涉及的也是最大的大小,而不仅仅是包含意义下极大的反链。一个无法再接受另一个子集的集族仍可能很小。例如,只含空子集的集族是包含意义下极大的,因为其他每个子集都包含它,但当基础集至少有两个元素时,它比中间层小。这并不矛盾:极大只是禁止一步扩张,而最大则是在所有集族之间比较。
常见错误
反例模式
LYM 不等式并不蕴含互不可比
在 上,集族 的权重为 ,但它的两个成员是可比的。正确的方向是:反链蕴含该不等式。仅有数值不等式不能证明反链性质,也不能用它代替对包含关系的检验。
常见错误
(空基础集仍有一个子集)
不要认为空基础集没有子集:它有空子集。当 时, 只有一个元素,所以最大反链是 ,大小为 。若把 当作空集,上界就会变成 ,偶数情形的取等结论也随之失效。
常见错误
(上影只看上一层,而非所有上集)
要区分下一层的上影与所有严格上集:上影证明中的关联度数依赖于恰好添加一个元素。在 上,单元素集 的上影是 ,共两个集,正好等于度数 。它的严格上集还包括 ;若把该集也计入,关联计数 就不再成立。
总结
对极大链的关联计数,证明了每个布尔反链所受的加权限制。最大的秩把它转化为 Sperner 的最优大小上界,而当两个中间秩并列时,上影扩张与连通性给出取等的分类。归一化的上影不等式保留了原始基数比较可能丢失的信息。
练习
快速检查
(列出三元基础集上的所有最大反链,并说明该列表是完整的。)
两个中间秩并列,因此使用已证明的取等分类。
解答 · 答案
最优大小为 。由奇数情形的取等结论,达到该大小的集族只有全部三个单元素集与全部三个二元子集。二者的确都是反链,所以两种情形都会出现。混合不同秩的集族可以是反链,但无法达到这个大小。
快速检查
(若六元基础集上的某个反链含有一个二元成员,证明它的大小至多为十九。)
利用该成员较大的权重。不要声称所得上界一定能够达到。
解答 · 答案
最大的层有 个成员,而所选的二元成员的权重为 。若集族的大小为 ,则其余每个成员的权重至少为 。于是 ,即 。由于 是整数,。这是在额外条件下的上界,并不是达到十九的构造。
快速检查
(在五元基础集上,选取三个单元素集。精确计算它们的上影,并与归一化上影下界比较。)
统计至少含有一个所选元素的二元子集。
解答 · 答案
二元子集共有 个。恰有一个避开全部三个所选元素:由两个未选元素构成的二元子集。因此上影含有九个二元子集。归一化不等式只给出上影大小至少为 。这个严格的差距反映出,大多数上影二元子集所含的所选单元素集,比关联上界中允许的两个要少。