A new short proof of the EKR theorem
From MaRDI portal
Publication:423657
DOI10.1016/J.JCTA.2012.03.012zbMATH Open1244.05008arXiv1108.2179OpenAlexW2156250987WikidataQ101132835 ScholiaQ101132835MaRDI QIDQ423657FDOQ423657
Authors: Peter Frankl, Zoltán Füredi 
Publication date: 4 June 2012
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1108.2179
Recommendations
shadowsmultilinear polynomialsgeneralized characteristic vectorsintersecting hypergraphsErdős-Ko-Rado
Cites Work
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersection theorems with geometric consequences
- Title not available (Why is that?)
- Intersection theorems for systems of finite sets
- The exact bound in the Erdős-Ko-Rado theorem
- Erdős-Ko-Rado from Kruskal-Katona
- A simple proof of the Erdős-Chao Ko-Rado theorem
- Erdös–Ko–Rado Theorem—22 Years Later
- A proof and generalizations of the Erdős-Ko-Rado theorem using the method of linearly independent polynomials
- Intersecting Families are Essentially Contained in Juntas
- On the measure of intersecting families, uniqueness and stability
- On t-designs
- Forestation in hypergraphs: Linear \(k\)-trees
- A sharp bound for the number of sets that pairwise intersect at \(k\) positive values
Cited In (34)
- A refined result on cross-intersecting families
- Tight bounds for Katona's shadow intersection theorem
- Erdős-Ko-Rado theorems in certain semilattices
- Restricted intersecting families on simplicial complex
- Shadows and intersections in vector spaces
- Intersecting families, signed sets, and injection
- Size and structure of large \((s,t)\)-union intersecting families
- The maximum sum of sizes of cross-intersecting families of subsets of a set
- New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- The maximum product of sizes of cross-intersecting families
- A Katona-type proof of an Erdős-Ko-Rado-type theorem
- A generalization of the Erdős-Ko-Rado theorem
- Title not available (Why is that?)
- EKR sets for large \(n\) and \(r\)
- Extremal \(G\)-free induced subgraphs of Kneser graphs
- Linear independence, a unifying approach to shadow theorems
- Title not available (Why is that?)
- Towards a Katona type proof for the \(2\)-intersecting Erdős-Ko-Rado theorem
- Sharp results concerning disjoint cross-intersecting families
- Old and new applications of Katona's circle
- On the arithmetic mean of the size of cross-union families
- The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- An improved universal bound for \(t\)-intersecting families
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- On intersecting families of independent sets in trees
- A new short proof of a theorem of Ahlswede and Khachatrian
- Beyond the Erdős-Ko-Rado theorem
- A short proof of Talbot's theorem for intersecting separated sets
- Erdös-Ko-Rado theorems for a family of trees
- Cross-intersecting subfamilies of levels of hereditary families
- An algebraic groups perspective on Erdős–Ko–Rado
- A note on supersaturated set systems
- Invitation to intersection problems for finite sets
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)
