A new short proof of the EKR theorem
classification
🧮 math.CO
keywords
familyproofintersectingk-subsetstheoremapplyingchooseclassical
read the original abstract
A family F is intersecting if any two members have a nonempty intersection. Erdos, Ko, and Rado showed that |F|\leq {n-1\choose k-1} holds for an intersecting family of k-subsets of [n]:={1,2,3,...,n}, n\geq 2k. For n> 2k the only extremal family consists of all k-subsets containing a fixed element. Here a new proof is presented. It is even shorter than the classical proof of Katona using cyclic permutations, or the one found by Daykin applying the Kruskal-Katona theorem.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.