Erdős–Ko–Rado 定理

Erdős–Ko–Rado定理
术语名称	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{ n-1 \choose k-1 }[/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{ t }[/math]-相交 [math]\displaystyle{ k }[/math]-集族中的元素数，若 [math]\displaystyle{ n \geq (t+1)(k-t+1) }[/math] 则最大不超过 [math]\displaystyle{ n-t \choose k-t }[/math] 个。