Sperner 定理
| Sperner定理 | |
|---|---|
| 术语名称 | Sperner定理 |
| 英语名称 | Sperner's theorem |
| Sperner系 | |
|---|---|
| 术语名称 | Sperner系 |
| 英语名称 | Sperner family |
| 别名 | antichain, clutter |
Sperner 系(Sperner family)指集合子集，其中的子集互不包含。 Sperner 定理(Sperner's theorem)指给定集合的 Sperner 系所含集合最大个数的定理。
定义
对集合的子集族，若集族内的子集两两不存在真包含关系，称为一个 Sperner 系(Sperner family of sets / clutter)，或者一个反链(antichain)。
定理
对一个大小为 [math]\displaystyle{ n }[/math] 的集合，其 Sperner 系中元素数最大不超过 [math]\displaystyle{ n \choose \lfloor n/2\rfloor }[/math] ； 当且仅当 Sperner 系中全部集合的元素个数都是 [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] 或都是 [math]\displaystyle{ \lceil n/2 \rceil }[/math] 时取等号。
序理论表述
对一个大小为 [math]\displaystyle{ n }[/math] 的集合，其幂集格中的最大反链的大小为 [math]\displaystyle{ n \choose \lfloor n/2\rfloor }[/math] ； 当且仅当反链由所有大小为 [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] 的子集或所有大小为 [math]\displaystyle{ \lceil n/2 \rceil }[/math] 的子集构成时达到该最大值。
是 Lubell–Yamamoto–Meshalkin 不等式的推论。
推论
- Erdős–Ko–Rado 定理：描述相交族的最大大小，是 Sperner 定理在相交条件下的推广。
- Kruskal–Katona 定理：给出给定数量的子集的最小阴影大小。