链与反链

链把所有元素压进一条可比较的时间线，反链则刻画任何线性次序都无法由原偏序强迫的并行层。高度与宽度因此分别测量最长依赖深度和不可避免的最大并发量。二者不是互补集合的概念：同一个元素可以属于许多不同的链和反链，真正有意义的是覆盖、分解与极值之间的关系。

布尔格 $2^{[n]}$ 中，按包含关系，$\varnothing \subset \{1\}\subset \cdots \subset [n]$ 是链；所有大小为 $\lfloor n/2\rfloor$ 的子集构成反链。整数整除偏序中，$1,2,4,8$ 是链，而 $2,3,5$ 是反链。全序中的每个子集都是链，最大反链大小为一。极小元集合是反链，但任意反链不必由极小元组成。无限偏序集的高度和宽度可能是无限基数，有限 Dilworth 定理的证明与推广需区分。

在任务偏序 $a<b<d$、$a<c<d$ 中，$\{a,b,d\}$ 是长度三的链，$\{b,c\}$ 是大小二的反链。至少需要两条链才能覆盖全部任务，例如 $a<b<d$ 与单点链 $c$；这与最大反链大小一致。若把“不可比较”误作“不相等”，全序中便会错误地把所有不同元素都视作反链。

在偏序公理库偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。中，Dilworth 定理公理库Dilworth 定理Dilworth's theorem有限偏序集的最大反链大小等于覆盖全部元素所需的最少链数。把最大反链大小等同于最少链覆盖数；对偶的 Mirsky 型结论把最大链长度联系到反链分层。布尔格中的中间层反链进一步通向 Sperner 理论，调度中则把链解释为顺序依赖、反链解释为可并行任务。格公理库格Lattice · Lattice order任意两元素都有最大下界与最小上界的偏序集。的秩层也常提供天然反链。