Dilworth 定理
| 迪尔沃斯定理 | |
|---|---|
| 术语名称 | 迪尔沃斯定理 |
| 英语名称 | Dilworth's theorem |
| 别名 | 偏序集分解定理 |
Dilworth 定理(Dilworth's theorem)或偏序集分解定理是关于偏序集最大最小的定理，偏序集最大反链元素个数等于其最小链划分的所需链个数。
其对偶是 Mirsky 定理。
定理
对有限偏序集 [math]\displaystyle{ (P, \leq) }[/math] ，偏序集 [math]\displaystyle{ P }[/math] 的宽度（最大反链的元素个数）等于其最小链划分（将 [math]\displaystyle{ P }[/math] 划分为反链的最少个数）。
与 Mirsky 定理的关系
Mirsky 定理与 Dilworth 定理互为对偶：
- Mirsky 定理：高度、最大链长度、最小反链划分数相等
- Dilworth 定理：宽度、最小反链长度、最小链划分数相等
| 序理论 | ||
|---|---|---|
| 预序、预序集 | 极大元、极小元 | 最大元、最小元 |
| 上界、下界 | 上确界、下确界 | |
| 方向、有向集 | 半格（并半格、交半格） | 有界半格（有界并半格、有界交半格） |
| 格 | 有界格 | |
| 偏序、偏序集 | Hasse 图 | |
| 链、长度、高度 | 反链、宽度 | |
| Dilworth 定理 | Mirsky 定理 | |