查看“︁狄尔沃斯定理”︁的源代码

{{Redirect|链划分|链剖分|轻重链剖分}}

{{Cleanup|time=2024-01-29T01:43:15+00:00}}
在[[数学]]中，在[[序理论]]和[[组合数学|组合学]]领域，'''狄尔沃斯定理'''通过将集合[[集合划分|划分]]为数目最少的[[全序关系|链]]来量化地描述任何有限[[偏序关系|偏序]]集的'''宽度'''。它以数学家{{harvs|txt|first=罗伯特|last=狄尔沃斯|authorlink=罗伯特·帕尔默·狄尔沃斯|year=1950|first2=帕尔默}} 命名。

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

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

== 归纳法证明（1） ==
下面通过在偏序集的大小施数学归纳法的证明来自{{Harvard citations|txt|last=加尔文|authorlink=弗莱德·加尔文|year=1994}}。

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

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

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

== 归纳法证明（2）==
下面的证明来自{{Harvard citation text|Perles|1963}}。

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

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

如果''P''中含有一个异于''A<sub>1</sub>''和''A<sub>2</sub>''的极大反链''A''，则我们定义''P''<sup>+</sup>为{''x''∈''P'': ∃''y''∈''A'' s.t. ''y''≤''x''}，''P''<sup>-</sup>为{''x''∈''P'': ∃''y''∈''A'' s.t. ''x''≤''y''}。根据''A''的极大性，''P''<sup>+</sup>∪''P''<sup>-</sup> =''P''。''A''是''P''<sup>+</sup>和''P''<sup>-</sup>的极大反链，根据归纳假设，可以取''P''<sup>+</sup>为''C''<sub>1</sub>∪...∪''C''<sub>m</sub>，''P''<sup>-</sup>为''D''<sub>1</sub>∪...∪''D''<sub>m</sub>，其中''C''<sub>i</sub>和''D''<sub>i</sub>为一系列链。易得''A''中元素为''C''<sub>i</sub>中的极小元、''D''<sub>i</sub>中的极大元。因此''C''<sub>i</sub>∪''D''<sub>i</sub>为P中的链。我们证明了''P''可以被''m''条链覆盖。

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

== 通过康尼锡定理证明 ==
[[File:Dilworth-via-König.svg|thumb|通过康尼锡定理证明狄尔沃斯定理定理：从偏序构造二部图，并根据匹配划分为链]]
与组合学中的许多其他结果一样，迪尔沃斯定理等价于[[二分图]]匹配的[[柯尼希定理 (图论)|康尼锡定理]]以及其他几个相关定理，包括[[霍爾婚配定理|霍尔婚配定理]]{{Harvard citation|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'' <sup>2</sup> ) 的时间中计算{{Harvard citation|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''色着色的不可比图，从而具有所需的链划分{{Harvard citation|Harzheim|2005}}   。

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

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

== 可比图的完美性质 ==
可比图是节点是偏序集中的点、两点间存在边当且仅当两点可比形成的[[图 (数学)|无向图]]。因此，可比图中的[[團 (圖論)|团]]就是链，可比图中的[[独立集]]就是反链。可比图的任何[[导出子图]]本身就是可比图，由偏序对其元素子集的限制形成。

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

== 特殊偏序的宽度 ==
[[布尔代数|布尔格]]''B'' <sub>''n''</sub>是''n''元集''X''的[[冪集|幂集]]（一般是 {1, 2, …, ''n''}），按[[子集]]关系赋偏序，可以用符号记作 (2 <sup>[ ''n'' ]</sup>, ⊆)。[[斯伯纳定理|斯佩纳定理]]指出，''B'' <sub>''n''</sub>的最大反链的大小为

: <math>\operatorname{width}(B_n) = {n \choose \lfloor{n/2}\rfloor}.</math>

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

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

关于单调子序列的[[Erdös -Szekeres定理|Erdős-Szekeres 定理]]可以解释为 Dilworth 定理在二维偏序上的应用{{Harvard citation|Steele|1995}}   。

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

== 参考 ==

* {{Citation|last=Berge|first=Claude|author1-link=Claude Berge|last2=Chvátal|first2=Václav|author2-link=Václav Chvátal|isbn=978-0-444-86587-8|page=viii|publisher=Elsevier|series=Annals of Discrete Mathematics|title=Topics on Perfect Graphs|volume=21|year=1984}}
* {{Citation|last=Dilworth|first=Robert P.|author-link=Robert P. Dilworth|title=A Decomposition Theorem for Partially Ordered Sets|jstor=1969503|journal=[[Annals of Mathematics]]|volume=51|number=1|pages=161–166|year=1950|doi=10.2307/1969503}}.
* {{Citation|last=Edelman|first=Paul H.|last2=Saks|first2=Michael E.|author2-link=Michael Saks (mathematician)|doi=10.1007/BF00143895|number=1|journal=[[Order (journal)|Order]]|pages=23–32|title=Combinatorial representation and convex dimension of convex geometries|volume=5|year=1988}}.
* {{Citation|last=Felsner|first=Stefan|last2=Raghavan|first2=Vijay|last3=Spinrad|first3=Jeremy|doi=10.1023/B:ORDE.0000034609.99940.fb|number=4|journal=[[Order (journal)|Order]]|mr=2079151|pages=351–364 (2004)|title=Recognition algorithms for orders of small width and graphs of small Dilworth number|volume=20|year=2003|url=https://refubium.fu-berlin.de/handle/fub188/18407|accessdate=2024-01-29|archive-date=2024-01-27|archive-url=https://web.archive.org/web/20240127121719/https://refubium.fu-berlin.de/handle/fub188/18407|dead-url=no}}.
* {{Citation|last=Fulkerson|first=D. R.|author-link=D. R. Fulkerson|title=Note on Dilworth's decomposition theorem for partially ordered sets|journal=[[Proceedings of the American Mathematical Society]]|volume=7|number=4|pages=701–702|year=1956|jstor=2033375|doi=10.2307/2033375}}.
* {{Citation|last=Galvin|first=Fred|author-link=Fred Galvin|title=A proof of Dilworth's chain decomposition theorem|mr=1270960|jstor=2975628|journal=[[American Mathematical Monthly|The American Mathematical Monthly]]|year=1994|volume=101|number=4|pages=352–353|doi=10.2307/2975628}}.
* {{Citation|last=Greene|first=Curtis|author1-link=Curtis Greene|last2=Kleitman|first2=Daniel J.|title=The structure of Sperner <math>k</math>-families|journal=Journal of Combinatorial Theory, Series A|volume=20|number=1|pages=41–68|year=1976|doi=10.1016/0097-3165(76)90077-7}}.
* {{Citation|last=Harzheim|first=Egbert|isbn=0-387-24219-8|place=New York|mr=2127991|at=Theorem&nbsp;5.6, p.&nbsp;60|publisher=Springer|series=Advances in Mathematics (Springer)|title=Ordered sets|url=https://books.google.com/books?id=FYV6tGm3NzgC&pg=PA59|volume=7|year=2005}}.
* {{Citation|last=Lovász|first=László|author-link=László Lovász|doi=10.1016/0012-365X(72)90006-4|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|pages=253–267|title=Normal hypergraphs and the perfect graph conjecture|volume=2|year=1972|number=3}}.
* {{Citation|author-link=Leon Mirsky|last=Mirsky|first=Leon|title=A dual of Dilworth's decomposition theorem|jstor=2316481|journal=[[American Mathematical Monthly]]|volume=78|number=8|year=1971|pages=876–877|doi=10.2307/2316481}}.
* {{Citation|last=Nešetřil|first=Jaroslav|author1-link=Jaroslav Nešetřil|last2=Ossona de Mendez|first2=Patrice|author2-link=Patrice Ossona de Mendez|chapter=Theorem 3.13|doi=10.1007/978-3-642-27875-4|isbn=978-3-642-27874-7|place=Heidelberg|mr=2920058|page=42|publisher=Springer|series=Algorithms and Combinatorics|title=Sparsity: Graphs, Structures, and Algorithms|volume=28|year=2012}}.
* {{Citation|last=Perles|first=Micha A.|author-link=Micha Perles|title=A proof of dilworth’s decomposition theorem for partially ordered sets|journal=[[Israel Journal of Mathematics]]|year=1963|volume=1|pages=105–107|doi=10.1007/BF02759805|number=2}}.
* {{Citation|last=Steele|first=J. Michael|author-link=J. Michael Steele|chapter=Variations on the monotone subsequence theme of Erdős and Szekeres|editor1-last=Aldous|editor1-first=David|editor1-link=David Aldous|editor2-last=Diaconis|editor2-first=Persi|editor2-link=Persi Diaconis|editor3-last=Spencer|editor3-first=Joel|editor3-link=Joel Spencer|postscript=3|editor4-last=Steele|editor4-first=J. Michael|editor4-link=J. Michael Steele|pages=111–131|publisher=Springer-Verlag|series=IMA Volumes in Mathematics and its Applications|title=Discrete Probability and Algorithms|url=http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf|volume=72|year=1995|accessdate=2024-01-29|archive-date=2019-06-11|archive-url=https://web.archive.org/web/20190611133100/http://www-stat.wharton.upenn.edu/%7Esteele/Publications/PDF/VOTMSTOEAS.pdf|dead-url=no}}.

== 外部链接 ==

* [http://robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics] {{Wayback|url=http://robertborgersen.info/Presentations/GS-05R-1.pdf |date=20210507025906 }}
* {{Citation
 |url=http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html 
 |title=Dual of Dilworth's Theorem 
 |work=[[PlanetMath]] 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20070714201213/http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html 
 |archive-date=2007-07-14 
}}
* {{Citation
 |author=Babai, László 
 |authorlink=László Babai 
 |url=http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf 
 |title=Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs 
 |year=2005 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20110720134637/http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf 
 |archive-date=2011-07-20 
}}
* {{Citation |author1=Felsner, S. |author2=Raghavan, V. |author3=Spinrad, J. |name-list-style=amp |year=1999 |title=Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number |url=http://www.inf.fu-berlin.de/inst/pubs/tr-b-99-05.abstract.html |postscript= |accessdate=2024-01-29 |archive-date=2012-02-05 |archive-url=https://web.archive.org/web/20120205114240/http://www.inf.fu-berlin.de/inst/pubs/tr-b-99-05.abstract.html |dead-url=no }}
* {{mathworld | title = Dilworth's Lemma | urlname = DilworthsLemma}}


{{序理论}}

[[Category:组合学]]
[[Category:序理论]]
[[Category:包含证明的条目]]