狄爾沃斯定理

在數學中，在序理論和組合學領域，狄爾沃斯定理通過將集合劃分為數目最少的鏈來量化地描述任何有限偏序集的寬度。它以數學家羅伯特狄爾沃斯（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.