狄尔沃斯定理

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

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

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

归纳法证明（1）

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

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

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

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

归纳法证明（2）

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

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

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

如果P中含有一个异于A₁和A₂的极大反链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⁺为C₁∪...∪C_m，P^-为D₁∪...∪D_m，其中C_i和D_i为一系列链。易得A中元素为C_i中的极小元、D_i中的极大元。因此C_i∪D_i为P中的链。我们证明了P可以被m条链覆盖。

如果P中没有异于A₁和A₂的极大反链，则设x属于A₁。设x≤y∈A₂。则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 ² ) 的时间中计算（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）。

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

\operatorname {width} (B_{n})={n \choose \lfloor {n/2}\rfloor }.

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

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

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

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

参考

Berge, Claude; Chvátal, Václav, Topics on Perfect Graphs, Annals of Discrete Mathematics 21, Elsevier: viii, 1984, ISBN 978-0-444-86587-8
Dilworth, Robert P., A Decomposition Theorem for Partially Ordered Sets, Annals of Mathematics, 1950, 51 (1): 161–166, JSTOR 1969503, doi:10.2307/1969503 .
Edelman, Paul H.; Saks, Michael E., Combinatorial representation and convex dimension of convex geometries, Order, 1988, 5 (1): 23–32, doi:10.1007/BF00143895 .
Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy, Recognition algorithms for orders of small width and graphs of small Dilworth number, Order, 2003, 20 (4): 351–364 (2004) [2024-01-29], MR 2079151, doi:10.1023/B:ORDE.0000034609.99940.fb, （原始内容存档于2024-01-27） .
Fulkerson, D. R., Note on Dilworth's decomposition theorem for partially ordered sets, Proceedings of the American Mathematical Society, 1956, 7 (4): 701–702, JSTOR 2033375, doi:10.2307/2033375 .
Galvin, Fred, A proof of Dilworth's chain decomposition theorem, The American Mathematical Monthly, 1994, 101 (4): 352–353, JSTOR 2975628, MR 1270960, doi:10.2307/2975628 .
Greene, Curtis; Kleitman, Daniel J., The structure of Sperner $k$ -families, Journal of Combinatorial Theory, Series A, 1976, 20 (1): 41–68, doi:10.1016/0097-3165(76)90077-7 .
Harzheim, Egbert, Ordered sets, Advances in Mathematics (Springer) 7, New York: Springer, Theorem 5.6, p. 60, 2005, ISBN 0-387-24219-8, MR 2127991 .
Lovász, László, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 1972, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4 .
Mirsky, Leon, A dual of Dilworth's decomposition theorem, American Mathematical Monthly, 1971, 78 (8): 876–877, JSTOR 2316481, doi:10.2307/2316481 .
Nešetřil, Jaroslav; Ossona de Mendez, Patrice, Theorem 3.13, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Heidelberg: Springer: 42, 2012, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 .
Perles, Micha A., A proof of dilworth’s decomposition theorem for partially ordered sets, Israel Journal of Mathematics, 1963, 1 (2): 105–107, doi:10.1007/BF02759805 .
Steele, J. Michael, Variations on the monotone subsequence theme of Erdős and Szekeres, Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (编), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications 72, Springer-Verlag: 111–131, 1995 [2024-01-29], （原始内容存档 (PDF)于2019-06-11）3 .

外部链接

Equivalence of seven major theorems in combinatorics （页面存档备份，存于互联网档案馆）
Dual of Dilworth's Theorem, PlanetMath, （原始内容存档于2007-07-14）
Babai, László, Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF), 2005, （原始内容 (PDF)存档于2011-07-20）
Felsner, S.; Raghavan, V. & Spinrad, J., Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number, 1999 [2024-01-29], （原始内容存档于2012-02-05）
埃里克·韦斯坦因. Dilworth's Lemma. MathWorld.