形式陈述

Dilworth 定理断言：对任意有限偏序集 $P$$P$，最大反链大小等于把 $P$$P$ 分割成链所需的最少链数，即

$$ w(P)=\min\{k:P\text{ 可分割为 }k\text{ 条链}\}. $$$$w(P)=min\{k:P\text{ 可分割为 }k\text{ 条链}\}.$$

一个方向直接来自鸽巢原理：任一链与反链至多相交一个元素，所以含 $w(P)$$w(P)$ 个元素的反链迫使任何链分解至少使用 $w(P)$$w(P)$ 条链。反方向可通过二分图最大匹配—最小顶点覆盖、归纳或最小链分解的交换论证证明。对偶的 Mirsky 定理称最少反链分解数等于最大链大小。

直觉

反链中的元素不能放进同一条链，因此给出并行槽位的下界；定理说明这个显然下界总能精确达到。

例子与边界

在任务依赖偏序中，宽度就是无限处理器下可同时进行的最大任务数，也是将任务分成顺序流水线所需的最少条数。布尔格的中间层反链由 Sperner 定理给出宽度，而 Dilworth 保证存在同样多条链的分解。定理中的“分割”要求每个元素恰属于一条链，不是仅用链覆盖允许重叠。有限性是本条版本的重要条件；无限偏序有需要选择原则和基数条件的推广，不能直接套用有限匹配证明。Dilworth 与 Mirsky 互为序关系反转意义下的相关结果，但结论中的链/反链分解方向不同。

推论与应用

Dilworth 定理连接偏序、匹配、调度和最小路径覆盖，是离散最小—最大对偶的经典实例。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Ex. 3.77(d), Dilworth’s theorem for finite posets。
• Garrett Birkhoff, Lattice Theory, 3rd ed., American Mathematical Society, 1967，Ch. V, decomposition theorems for partially ordered sets。