林庆泽

(广州大学 物理与电子工程学院, 广东 广州 510006)

Erdøs-Ko-Rado定理的一个新证明

林庆泽

(广州大学 物理与电子工程学院, 广东 广州 510006)

Erdøs-Ko-Rado定理是极值组合学里非常基础也非常重要的定理，它给出了自相交有限子集族里基数大小的上界的一个非常好的估计，在集合论和图论等相关领域有很多应用.证明方法很多，既有组合方面的，也有代数方面的.通过构建某些集合族间的2种单射以及一些相关的性质，诸如自相交性，给出了该定理的另一种证明方法.

组合学;Erdøs-Ko-Rado定理;子集族;自相交性

0 引 言

Erdøs-Ko-Rado定理，简称EKR定理，主要研究子集族的自相交性质,是研究有限集的自相交子集族的最原始成果,也是极值组合学理论中最重要的结论之一.近年来,许多著名数学家研究了EKR定理及其各种推广[1-3],例如，给出了EKR定理在各种偏序集上的极值结构的刻画[4]，通过研究偏序集的EKR性质，进而证明了Coxeter群的严格EKR性质等[5].作为相交有限子集族基数大小的上界的一个非常好的估计，EKR定理为集合论、组合学、代数学和图论等学科及其相关交叉学科的相关研究工作提供了很多极为有用的帮助.EKR定理由Erdøs、Ko及Rado3位数学家首次给出归纳证明[6]，之后数学家Katona利用代数里的循环置换给出了该定理的一个更简洁的证明[7].本研究通过构建某些集合族间的2种单射以及一些相关的性质，诸如自相交性和不变性等，给出了EKR定理的另一种证明方法.

1 预备知识

因此，命题成立.证毕.

其中，Δ(Ω，N2a)为集合Ω，N2a的对称差……