Dilworth 定理

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

在任务依赖偏序中，宽度是两两互不依赖的任务组的最大大小，也是将全部任务分割成依赖链所需的最少链数。布尔格的中间层反链由 Sperner 定理给出宽度，而 Dilworth 保证存在同样多条链的分解。定理中的“分割”要求每个元素恰属于一条链。本条讨论有限偏序；无限偏序的推广另涉及选择原则与基数条件。Mirsky 定理则把最大链大小与最少反链分割数配对，交换了链与反链在结论中的角色。

在除法偏序 $\{1,2,3,6\}$ 中，最大反链可取 $\{2,3\}$，大小为二；两条链 $1<2<6$ 与单点链 $3$ 覆盖全部元素。任何一条链都无法同时包含 $2,3$，所以一条不够。

将 $P$ 的元素复制为左右两份，在 $x<y$ 时连接 $x_L$ 与 $y_R$。一组匹配理路匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。为每个元素指定至多一个前驱和后继；严格偏序排除了有向环，因此这些连接组成链分割。若匹配有 $m$ 条边，就得到 $|P|-m$ 条链。

反过来，在每条链内连接相邻元素，含 $k$ 条链的分割给出大小 $|P|-k$ 的匹配。所以最大匹配数 $\nu$ 对应最少链数 $|P|-\nu$。再由Kőnig 定理理路Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。取一个大小为 $\nu$ 的顶点覆盖 $C$，定义 $A=\{x\in P:x_L\notin C,x_R\notin C\}$。若 $x<y$ 且两者都在 $A$，边 $x_L{y}_R$ 就未被覆盖，矛盾；所以 $A$ 是反链。覆盖的 $\nu$ 个副本至多涉及 $\nu$ 个原元素，故 $|A|\ge |P|-\nu$。另一方面，任何反链与每条链至多相交一次，刚构造的 $|P|-\nu$ 条链又给出 $|A|\le w(P)\le |P|-\nu$。上下界因此相等，完成反向证明，也产生同值的链分割与反链证书。空偏序取空匹配、空覆盖和空反链，同样成立。

对有限个非空半开区间 $[s_x,f_x)$（$s_x<f_x$），定义 $x<y$ 当且仅当 $f_x\le s_y$，链就是能顺次共用一份资源的区间组，反链就是两两重叠的区间组。完美图理路完美图Perfect graph每个顶点诱导子图的色数都等于最大团大小；区间图可用资源分配与同时重叠证书证明这一性质。给出六个区间的具体证书：三条链 $\{A,E\}$、$\{B,D\}$、$\{C,F\}$ 覆盖全部任务，反链 $\{A,B,C\}$ 证明三条已最少。连接不可比较元素得到的图中，链是颜色类，反链是团；将 Dilworth 定理用于每个元素子集，便得到不可比较图的完美性。