偏序集分解定理
(重定向自Dilworth 定理)
偏序集分解定理 | |
---|---|
术语名称 | 偏序集分解定理 |
英语名称 | Dilworth's theorem |
别名 | 狄尔沃斯定理 |
偏序集分解定理/狄尔沃斯定理(Dilworth's theorem)是关于偏序集最大最小的定理,偏序集最大反链元素个数等于其最小链划分的所需链个数。
其对偶是 Mirsky 定理。
是组合数学三大存在性定理之一。
定理
偏序集的宽度,即偏序集反链(无关的子集)中的最大元素个数,等于其划分成链(全序的子集)的最小个数。
序理论 | ||
---|---|---|
预序、预序集 | 极大元、极小元 | 最大元、最小元 |
上界、下界 | 上确界、下确界 | |
方向、有向集 | 半格(并半格、交半格) | 有界半格(有界并半格、有界交半格) |
格 | 有界格 | |
偏序、偏序集 | Hasse 图 | |
链、长度、高度 | 反链、宽度 | |
Dilworth 定理 | Mirsky 定理 |