查看“︁Sperner 定理”︁的源代码

[[分类:序理论]]
[[分类:极值集合论]]
[[分类:以 Sperner 命名]]{{DEFAULTSORT:sperner ding4li3}}
{{#seo:
|keywords=Sperner定理, Sperner系, 互不包含子集最大数量
|description=本文介绍Sperner定理的定义、内容和证明，包括Sperner系定义为集合的互不包含子集，作为幂集格中反链的概念，以及n元集合的最大反链大小的极值性质。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-03-02
}}
{{InfoBox
|name=Sperner定理
|eng_name=Sperner's theorem
}}
{{InfoBox
|name=Sperner系
|eng_name=Sperner family
|aliases=antichain,clutter
}}
'''Sperner 系'''('''Sperner family''')指[[集合]]的互不包含子集。
'''Sperner 定理'''('''Sperner's theorem''')指给定集合的 Sperner 系所含集合最大个数的定理。

== 定理 ==

对集合的子集族，若集族内的子集两两不存在真包含关系，称为一个'''Sperner 系'''('''Sperner family''' of sets / '''clutter''')，或者一个'''反链'''('''antichain''')。

对一个大小为 <math>n</math> 的集合，其 Sperner 系中元素数最大不超过 <math>n \choose \lfloor n/2\rfloor</math> ；
当且仅当 Sperner 系中全部集合的元素个数都是 <math>\lfloor n/2 \rfloor</math> 或都是 <math>\lceil n/2 \rceil</math> 时取等号。

=== 序理论表述 ===

对集合的幂集格，定义其中的反链为 Sperner 系。

对一个大小为 <math>n</math> 的集合，其幂集格中的最大反链的大小为 <math>n \choose \lfloor n/2\rfloor</math> ；
当且仅当反链由所有大小为 <math>\lfloor n/2 \rfloor</math> 的子集或所有大小为 <math>\lceil n/2 \rceil</math> 的子集构成时达到该最大值。

是 [[Lubell–Yamamoto–Meshalkin 不等式]]的推论。

== 推论 ==

* [[Erdős–Ko–Rado 定理]]：描述相交族的最大大小，是 Sperner 定理在相交条件下的推广。
* [[Kruskal–Katona 定理]]：给出给定数量的子集的最小阴影大小。