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] 时取等号。
序理论表述
对集合的幂集格，定义其中的反链为 Sperner 系。
对一个大小为 [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 定理：给出给定数量的子集的最小阴影大小。