跳转到内容

狄尔沃斯定理

维基百科，自由的百科全书
  「链划分」重定向至此。关于链剖分，请见「轻重链剖分」。

在数学中，在序理论和组合学领域，狄尔沃斯定理通过将集合划分为数目最少的链来量化地描述任何有限偏序集的宽度。它以数学家罗伯特 狄尔沃斯 （1950） 命名。

偏序集中的反链是其元素两两不可比的子集，而链是其元素两两可比的子集。链分解是将偏序集中的元素划分为若干无交的链。狄尔沃斯定理指出，有限偏序集合中，包含元素最多反链的元素数等于包含链数最少的链分解的链数，这个量被定义为该偏序集的宽度。

将这个定理推广到无限偏序集：如果存在有限多个链的分解，或当反链的大小有有限的上界时，最大反链和最小链分解的大小仍然相等。

归纳法证明（1）

[编辑]

下面通过在偏序集的大小施数学归纳法的证明来自 加尔文 （1994）。

设P是有限偏序集。如果P是空集，狄尔沃斯定理是显然的。所以设P非空，并取其极大元a。

通过归纳法，设整数k，使得偏序集P':=P\{a}可以被k个不相交的链C1,C2,...,Ck覆盖，同时存在至少一个反链A0包含k个元素。显然，对于任意i=1,2,...,k，A0∩Ci≠∅。对于任意i=1,2,...,k，设xi是满足在中某一个大小为k的反链中且包含于Ci中的所有元素中的极大元，并设集合A:={x1,x2,...,xk}。首先我们证明A是一个反链：设Ai是包含xi的大小为k的反链。固定两个不同的编号i和j ，有Ai∩Cj≠∅ 。设y∈Ai∩Cj，则y≤xj（xj的定义）。这说明xi≥xj 不成立（因为xi≥y不成立）。通过在上述证明中交换i和j，可得xj≥xi 不成立。于是我们证明了A是一个反链。

现在我们讨论P是否满足狄尔沃斯定理。如果存在i=1,2,...,k使得a≥xi。设K是链{a}∪{z∈Ci:z≤xi}，由于xi的选取，P\K中不存在大小为k的反链 。根据归纳假设，P\K可以被k-1个无交的链覆盖，这是因为在P\K中，A\{xi}是大小为k-1的反链。因此，P可以被k条无交的链覆盖，这便是狄尔沃斯定理所言。否则，如果对于任意i=1,2,...,k都有a≥xi不存在 ， 则A∪{a}是P中大小为k+1的反链 （因为a是P中的极大元）。因此，P可以被k+1条链{a},C1,C2,...,Ck覆盖，得证。

归纳法证明（2）

[编辑]

下面的证明来自Perles (1963)。

由于P中每一条链最多包含一个反链中元素（链、反链的定义），所以P中最小链覆盖链数大于等于最大反链长度。

同样对P的大小n采用归纳法。设P中的最大反链长度为m。我们只需证明P中最小链覆盖链数大于等于最大反链长度，即P可以被m条链覆盖。记A1和A2为P中的所有极大元和极小元组成的集合。我们对P的性质进行分类讨论：

如果P中含有一个异于A1和A2的极大反链A，则我们定义P+为{x∈P: ∃y∈A s.t. y≤x}，P-为{x∈P: ∃y∈A s.t. x≤y}。根据A的极大性，P+∪P- =P。A是P+和P-的极大反链，根据归纳假设，可以取P+为C1∪...∪Cm，P-为D1∪...∪Dm，其中Ci和Di为一系列链。易得A中元素为Ci中的极小元、Di中的极大元。因此Ci∪Di为P中的链。我们证明了P可以被m条链覆盖。

如果P中没有异于A1和A2的极大反链，则设x属于A1。设x≤y∈A2。则P\{x,y}的最大反链长为m-1。根据归纳假设，P\{x,y}可以被m-1条链覆盖。再加上{x,y}这一条链，一共m条链得证。

通过康尼锡定理证明

[编辑]
通过康尼锡定理证明狄尔沃斯定理定理：从偏序构造二部图，并根据匹配划分为链

与组合学中的许多其他结果一样，迪尔沃斯定理等价于二分图匹配的康尼锡定理以及其他几个相关定理，包括霍尔婚配定理(Fulkerson 1956) 。

为了证明包含n个元素的偏序集S上狄尔沃斯定理，考虑使用康尼锡定理，定义二分图G = (U, V, E) ，其中U = V = S ，且(u, v)是G中的一条边当且仅当在S中u < v成立。根据康尼锡定理， G中存在匹配M 以及一组顶点C ，使得图G中的每条边至少包含C中的一个顶点，并且M和C包含的元素个数一样多，这个值记为m 。设A为S中不对应于C中任何顶点的元素集合，则A至少有n - m个元素（如果C包含至少一个对应于二分图两侧相同元素的顶点，则这个值可能更多），且A的元素两两不可比。使用对于每一条M的边 ( x, y )，合并链x，y来生成链组成的集合P；则P有n - m条链。因此，我们构建了一个一条反链和一个具有相同元素个数的链划分。

为了用狄尔沃斯定理证明康尼锡定理，固定二分图G = ( U, V, E )，在U∪V上构造一个偏序：u < v当且仅当u∈U，v∈V，且E中存在一条从u到v的边。根据迪尔沃斯定理，存在一条反链A和一个链划分P，两者包含的元素个数相同。但偏序中唯一的非平凡链是与图中的边(u,v)对应的链u-v，因此P中的非平凡链在图中形成匹配。且反链A的补集是G中的顶点覆盖，其基数与此匹配相同。

这种偏序宽度与二分匹配的互相转化使得我们可以在多项式时间内计算任意偏序的宽度。更准确地说，宽度为k 的n元偏序的可以在O ( kn 2 ) 的时间中计算(Felsner, Raghavan & Spinrad 2003) 。

无限偏序集上的扩展

[编辑]

无限偏序集上的迪尔沃斯定理指出，当且仅当它可以划分为w个链时，偏序集才具有有限宽度w 。例如，假设无限偏序P的宽度为w ，这意味着任何反链中至多有有限个元素，且其上界为w 。对于P的任何子集S ，将S分解为w条链（如果存在）可以被描述为S的不可比图的着色（以S的元素为顶点的图，每两个不可比元素之间有一条边）需要用w种颜色；不可比图的正规着色中的每个颜色类都必须是一条链。假设P的宽度为w ，并且根据迪尔沃斯定理的有限版本， P的每个有限子集S都有一个可使用w色着色的不可比图。因此，根据De Bruijn-Erdős 定理， P本身也有可使用w色着色的不可比图，从而具有所需的链划分(Harzheim 2005) 。

然而，该定理并不能简单地扩展到无限宽（而非基数无限）的偏序集上。在这种情况下，最大反链的大小和覆盖偏序所需的最小链数可能有基数上的差异。特别地，对于每个无限基数κ ，都有一个宽度为ℵ 0的无限偏序集，其划分为最少的链有 κ 链(Harzheim 2005)。

对偶狄尔沃斯定理

[编辑]
主条目：米尔斯基定理

对偶迪尔沃斯定理指出，偏序集中最大链的大小（如果有限）等于该序可以划分成的反链的最小数量(Mirsky 1971) 。这个证明比迪尔沃斯定理本身的证明简单得多：对于任何元素x ，考虑以x为其最大元素的链，并令N ( x ) 表示这些x最大链中最大的链的大小，称为x的层数。可以证明每一条链从最小元到最大元的层数经过一个区间的层。所以同层的元素构成一条反链，而最长的链恰好等于整个偏序集的最大层数。

可比图的完美性质

[编辑]

可比图是节点是偏序集中的点、两点间存在边当且仅当两点可比形成的无向图。因此，可比图中的团就是链，可比图中的独立集就是反链。可比图的任何导出子图本身就是可比图，由偏序对其元素子集的限制形成。

如果在每个导出子图中，色数等于最大团的大小，则无向图是完美的。这就是图论版本的米尔斯基定理(Berge & Chvátal 1984)。根据Lovász (1972)的完美图定理，任何完美图的补图也是完美的。因此，任何可比图的补集都是完美的；这就是迪尔沃斯定理的图论版本(Berge & Chvátal 1984) 。因此，完美图对取补的封闭性可以用另一种方式证明迪尔沃斯定理。

特殊偏序的宽度

[编辑]

布尔格B n是n元集X的幂集（一般是 {1, 2, …, n}），按子集关系赋偏序，可以用符号记作 (2 [ n ], ⊆)。斯佩纳定理指出，B n的最大反链的大小为

换句话说，X的[n/2]元子集全体就是X的最大反链。 Lubell-Yamamoto-Meshalkin 不等式也涉及幂集中的反链，可用于证明斯佩纳定理。

如果我们对区间 [1, 2n] 中的整数按整除性赋序，则子区间 [n + 1, 2n] 形成基数为n的反链。将此偏序划分为n条链很容易：对每个奇数整数m ，{m2i}都是一条链。因此，根据迪尔沃斯定理，该偏序的宽度为n 。

关于单调子序列的Erdős-Szekeres 定理可以解释为 Dilworth 定理在二维偏序上的应用(Steele 1995) 。

定义反拟阵的“凸维数”：定义反拟阵所需的最小链数。于是我们可以使用迪尔沃斯定理来表明它等于其相关偏序的宽度；这种转化可以制成计算凸维数的多项式时间算法(Edelman & Saks 1988)。

参考

[编辑]

外部链接

[编辑]


检索自“https://zh.wikipedia.org/w/index.php?title=狄尔沃斯定理&oldid=82333065”