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 定理：给出给定数量的子集的最小阴影大小。