查看“︁Erdős–Ko–Rado 定理”︁的源代码

[[分类:序理论]]
[[分类:极值集合论]]
[[分类:以 Erdős 命名]]
[[分类:以柯召命名]]
[[分类:以 Rado 命名]]{{DEFAULTSORT:erdos ko rado ding4li3}}
{{#seo:
|keywords=Erdős–Ko–Rado定理, 星形结构
|description=本文介绍Erdős–Ko–Rado定理的内容，包括相交k-集族的最大大小确定，星形结构的极值性质。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-03-02
}}
{{InfoBox
|name=埃尔德什–柯–拉多定理
|eng_name=Erdős–Ko–Rado theorem
}}
'''Erdős–Ko–Rado 定理'''('''Erdős–Ko–Rado theorem''')指关于[[集合]]中两两相交子集的最大个数的定理。

== 定理 ==

对集合的子集族，若集族内每个集合大小都为 <math>k</math> ，且每两个集合都相交，称为一个'''相交 <math>k</math>-集族'''。

对一个大小为 <math>n</math> 的集合及正整数 <math>k</math> ，满足 <math>n \geq 2k</math> ，则集合上任意相交 <math>k</math>-集族的最大大小为 <math>n-1 \choose k-1</math> 个。
当 <math>n > 2k</math> 时，取得最大值当且仅当相交族构成“星形结构(star)”，即所有子集都包含一个固定元素；当 <math>n=2k</math> 时存在非星形的构造。

注：若 <math>n < 2k</math> 则任取两个 <math>k</math> 个元素的集合一定相交，此时最大不超过 <math>n \choose k</math> 个。

=== 扩展 ===

对集合的子集族，若集族内每个集合大小都为 <math>k</math> ，且每两个集合都相交且交集大小至少为 <math>t</math> ，称为一个'''<math>t</math>-相交 <math>k</math>-集族'''。

对一个大小为 <math>n</math> 的集合及正整数 <math>k, t</math> ，满足 <math>n \geq (t+1)(k-t+1)</math> ，则集合上任意 <math>t</math>-相交 <math>k</math>-集族中的最大大小为 <math>n-t \choose k-t</math> 个。