Sperner 定理
| Sperner定理 | |
|---|---|
| 术语名称 | Sperner定理 |
| 英语名称 | Sperner's theorem |
| 别名 | Sperner引理, Sperner's lemma |
| 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] 的集合，其反链中的元素数最大不超过 [math]\displaystyle{ n \choose \lfloor n/2\rfloor }[/math] ，且仅当反链中的全部集合都有 [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] 个或都有 [math]\displaystyle{ \lceil n/2 \rceil }[/math] 个元素时取等号。