Dilworth 定理

定理把一个极大“横截面”与覆盖整个偏序所需的最少“纵线”精确配平。下界显然：一条链至多包含反链中的一个元素；困难在于证明这个障碍已经是唯一障碍，总能用恰好宽度条链覆盖。匹配证明把“某元素可接到更大元素”编码为二分图边，使链首尾拼接转化为匹配大小。

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

在除法偏序 $\{1,2,3,6\}$ 中，最大反链可取 $\{2,3\}$，大小为二；两条链 $1<2<6$ 与单点链 $3$ 覆盖全部元素。任何一条链都无法同时包含 $2,3$，所以一条不够。注意“划分为链”要求每个元素恰出现一次；允许重叠覆盖不会降低由反链给出的下界，但会模糊等号的组合含义。

它以链与反链为极值对象，并可通过Hall 婚配定理公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。或最大匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。证明。任务依赖偏序中，最少处理器链数等于最大同时不可比较任务数；在二分图中，这条对应又通向Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。和最小路径覆盖算法。