Abstract: A family F is intersecting if any two members have a nonempty intersection. Erdos, Ko, and Rado showed that |F|leq {n-1choose k-1} holds for an intersecting family of k-subsets of [n]:={1,2,3,...,n}, ngeq 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3621717 (Why is no real title available?)
- A proof and generalizations of the Erdős-Ko-Rado theorem using the method of linearly independent polynomials
- A sharp bound for the number of sets that pairwise intersect at \(k\) positive values
- A simple proof of the Erdős-Chao Ko-Rado theorem
- Erdös–Ko–Rado Theorem—22 Years Later
- Erdős-Ko-Rado from Kruskal-Katona
- Forestation in hypergraphs: Linear \(k\)-trees
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersecting Families are Essentially Contained in Juntas
- Intersection theorems for systems of finite sets
- Intersection theorems with geometric consequences
- On t-designs
- On the measure of intersecting families, uniqueness and stability
- The exact bound in the Erdős-Ko-Rado theorem
Cited in
(34)- Cross-intersecting subfamilies of levels of hereditary families
- The maximum sum of sizes of cross-intersecting families of subsets of a set
- Shadows and intersections in vector spaces
- An improved universal bound for \(t\)-intersecting families
- On the arithmetic mean of the size of cross-union families
- An algebraic groups perspective on Erdős–Ko–Rado
- scientific article; zbMATH DE number 4152430 (Why is no real title available?)
- EKR sets for large \(n\) and \(r\)
- A Katona-type proof of an Erdős-Ko-Rado-type theorem
- Old and new applications of Katona's circle
- Beyond the Erdős-Ko-Rado theorem
- Intersecting families, signed sets, and injection
- A generalization of the Erdős-Ko-Rado theorem
- A refined result on cross-intersecting families
- The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities
- Invitation to intersection problems for finite sets
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Towards a Katona type proof for the \(2\)-intersecting Erdős-Ko-Rado theorem
- Tight bounds for Katona's shadow intersection theorem
- New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- Erdös-Ko-Rado theorems for a family of trees
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- Restricted intersecting families on simplicial complex
- On intersecting families of independent sets in trees
- Extremal \(G\)-free induced subgraphs of Kneser graphs
- The maximum product of sizes of cross-intersecting families
- Sharp results concerning disjoint cross-intersecting families
- A short proof of Talbot's theorem for intersecting separated sets
- A note on supersaturated set systems
- Erdős-Ko-Rado theorems in certain semilattices
- Size and structure of large \((s,t)\)-union intersecting families
- scientific article; zbMATH DE number 2212132 (Why is no real title available?)
- A new short proof of a theorem of Ahlswede and Khachatrian
- Linear independence, a unifying approach to shadow theorems
This page was built for publication: A new short proof of the EKR theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423657)
