Erdős–Ko–Rado 定理

埃尔德什–柯–拉多定理
术语名称	埃尔德什–柯–拉多定理
英语名称	Erdős–Ko–Rado theorem

Erdős–Ko–Rado 定理(Erdős–Ko–Rado theorem)指关于集合中两两相交子集的最大个数的定理。

定理

对集合的子集族，若集族内每个集合大小都为 [math]\displaystyle{ k }[/math] ，且每两个集合都相交，称为一个相交 [math]\displaystyle{ k }[/math]-集族。

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

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

扩展

对集合的子集族，若集族内每个集合大小都为 [math]\displaystyle{ k }[/math] ，且每两个集合都相交且交集大小至少为 [math]\displaystyle{ t }[/math] ，称为一个[math]\displaystyle{ t }[/math]-相交 [math]\displaystyle{ k }[/math]-集族。

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