反链
| 反链 | |
|---|---|
| 术语名称 | 反链 |
| 英语名称 | antichain |
| 宽度 | |
|---|---|
| 术语名称 | 宽度 |
| 英语名称 | width |
反链(antichain)指偏序集中的不可比子集，表现为其 Hasse 图中不存在纵向连线关系的结点。 其中的元素数称为其宽度(width)。 偏序集的最大反链宽度也称为偏序集的宽度(width)。
定义
对偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 及其子集 [math]\displaystyle{ A\subseteq P }[/math] ，若 [math]\displaystyle{ (\forall x, y \in A)(x\neq y \rightarrow x \npreceq y \land y \npreceq x) }[/math] ，即 [math]\displaystyle{ \preceq|_A }[/math] 是 [math]\displaystyle{ A }[/math] 上的一个恒等关系，则称 [math]\displaystyle{ A }[/math] 是偏序集中的一个反链(antichain)。 称反链中元素的个数，即 [math]\displaystyle{ \operatorname{card}A }[/math] 为其宽度(width)。
偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 的全部反链中的最大宽度称为偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 的宽度(width)。
性质
反链具有以下重要性质：
- 反链是偏序集中的不可比子集，任意两个不同元素都不可比较。
- 空集视为空反链。
- 单元素集一定是反链，是平凡反链。
- 运算性质
- 与链概念定义正相对
- 相关定理
- Dilworth 定理（偏序集分解定理）：偏序集的最小链划分等于最大反链的大小
- Mirsky 定理：偏序集的最小反链划分等于最大链的大小
- Sperner 定理：在幂集格中，最大反链由大小居中的子集构成
| 序理论 | ||
|---|---|---|
| 预序、预序集 | 极大元、极小元 | 最大元、最小元 |
| 上界、下界 | 上确界、下确界 | |
| 方向、有向集 | 半格（并半格、交半格） | 有界半格（有界并半格、有界交半格） |
| 格 | 有界格 | |
| 偏序、偏序集 | Hasse 图 | |
| 链、长度、高度 | 反链、宽度 | |
| Dilworth 定理 | Mirsky 定理 | |