链与反链

链描述一组被原偏序排定先后的对象，反链描述一组原偏序没有规定两两先后的对象。在任务依赖模型中，链给出必须串行经历的依赖深度，反链给出彼此没有先后约束的任务集合。不过，“没有依赖”不等于实际必然同时执行：资源数量和任务持续时间仍会限制调度。

链与反链也不是互补集合。一个元素可以出现在许多不同的链和反链中；单点集甚至同时是链和反链。两者真正的制约是：任一链与任一反链最多共享一个元素。若共享两个不同元素，它们就会同时被要求可比和不可比，产生矛盾。

在布尔偏序集 $2^{[n]}$ 中，底集元素是 $[n]=\{1,\dots ,n\}$ 的子集，偏序为包含关系。$\varnothing \subset \{1\}\subset \cdots \subset [n]$ 是含 $n+1$ 个元素的链。所有大小为 $\lfloor n/2\rfloor$ 的子集构成反链，因为两个不同的等大小有限集不可能一方包含另一方。正整数按整除排序时，$1,2,4,8$ 是链，而 $2,3,5$ 是反链。

在任务偏序 $a<b<d$、$a<c<d$ 中，$\{a,b,d\}$ 是大小三的链，$\{b,c\}$ 是大小二的反链。链分解可以取 $\{a,b,d\}$ 与 $\{c\}$；由反链 $\{b,c\}$ 可知一条链不可能覆盖全部元素。因此该例的高度为三，宽度为二。

极大不一定最大。令偏序集由一条三元素链 $a<b<c$ 和一个与它们全部不可比的元素 $z$ 组成，则 $\{z\}$ 已是极大链，但最大链为 $\{a,b,c\}$。全序的每个子集都是链，非空全序的宽度为一；所以不能把“不可比”误读成“不相等”。所有极小元组成反链，但反链未必只含极小元。

无限情形不能直接照搬上述有限最大值。例如，把长度分别为 $1,2,3,\dots$ 的有限链不交并在一起，并规定不同链之间不可比，则链大小无有限上界，却没有无限链。此时必须区分上确界与能取到的最大基数。

Dilworth 定理理路Dilworth 定理Dilworth's theorem有限偏序集的最大反链大小等于覆盖全部元素所需的最少链数。说明有限偏序集的宽度恰等于最少链分解数；“至少需要宽度那么多条链”正是由链与反链至多交于一点得到的。另一方向是该定理的实质。

相应的反链分层结论可直接证明。令 $r(x)$ 为以 $x$ 结尾的最大链大小；若 $x<y$，则 $r(y)\ge r(x)+1$。因此同一 $r$ 值的元素组成反链，总共至多 $h(P)$ 层；而最大链的元素又必须分在不同层，故最少反链分解数恰为 $h(P)$。这也解释了单位时长、处理器无限的依赖调度为什么需要且只需这么多轮。

布尔格的中间层反链通向 Sperner 定理。一般格理路格Lattice · Lattice order任意两元素都有最大下界与最小上界的偏序集。若另有严格随序增加的秩函数，同秩元素也形成反链；不能仅因一个偏序集是格就默认它具有统一的秩层。