New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
From MaRDI portal
Publication:1744762
DOI10.1016/J.DISC.2018.03.010zbMATH Open1384.05151arXiv1609.04714OpenAlexW2964303041WikidataQ113877058 ScholiaQ113877058MaRDI QIDQ1744762FDOQ1744762
Authors: Vikram Kamat, Glenn H. Hurlbert 
Publication date: 19 April 2018
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: A set system F is intersecting if any pair of sets in F have a nonempty intersection. A fundamental theorem of ErdH{o}s, Ko and Rado states that if F is an intersecting family of r-subsets of [n]={1,...,n}, and n>= 2r, then the cardinality of F is at most the cardinality of the family of all r-subsets of [n] containing a fixed element. Furthermore, when n>2r, equality holds if and only if F is the family of all r-subsets of [n] containing a fixed element. This characterization was proved as part of a stronger result by Hilton and Milner. In this note, we provide new injective proofs of the ErdH{o}s--Ko--Rado and the Hilton--Milner theorems.
Full work available at URL: https://arxiv.org/abs/1609.04714
Recommendations
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- A simple proof of the Hilton-Milner theorem
- A new short proof of the EKR theorem
- A Katona-type proof of an Erdős-Ko-Rado-type theorem
- Intersecting families, signed sets, and injection
Cites Work
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Erdős-Ko-Rado theorems. Algebraic approaches
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Intersection theorems for systems of finite sets
- Title not available (Why is that?)
- Non-trivial intersecting families
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- A new short proof of the EKR theorem
- Maximum hitting of a set by compressed intersecting families
- 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
- Some best possible inequalities concerning cross-intersecting families
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Extremal t -intersecting sub-families of hereditary families
- Non-trivial intersecting uniform sub-families of hereditary families
- Invitation to intersection problems for finite sets
- Strongly intersecting integer partitions
Cited In (17)
- On strengthenings of the intersecting shadow theorem
- Intersecting families, signed sets, and injection
- Maximum hitting of a set by compressed intersecting families
- 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
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- Some Erdős-Ko-Rado theorems for injections
- Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- A product version of the Hilton-Milner theorem
- Improved bounds on the maximum diversity of intersecting families
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- On intersecting families of independent sets in trees
- A simple proof of the Hilton-Milner theorem
- Cross-intersecting subfamilies of levels of hereditary families
- Non-trivial \(d\)-wise intersecting families
This page was built for publication: New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1744762)
