New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
From MaRDI portal
Publication:1744762
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.
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
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- scientific article; zbMATH DE number 3489128 (Why is no real title available?)
- scientific article; zbMATH DE number 2176112 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- A new short proof of the EKR theorem
- 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
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Erdős-Ko-Rado theorems. Algebraic approaches
- Extremal t -intersecting sub-families of hereditary families
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersection theorems for systems of finite sets
- Invitation to intersection problems for finite sets
- Maximum hitting of a set by compressed intersecting families
- Non-trivial intersecting families
- Non-trivial intersecting uniform sub-families of hereditary families
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Some best possible inequalities concerning cross-intersecting families
- Strongly intersecting integer partitions
Cited in
(17)- Cross-intersecting subfamilies of levels of hereditary families
- On the arithmetic mean of the size of cross-union families
- Old and new applications of Katona's circle
- Intersecting families, signed sets, and injection
- Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
- Improved bounds on the maximum diversity of intersecting families
- A simple proof of the Hilton-Milner theorem
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- On strengthenings of the intersecting shadow theorem
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- Some Erdős-Ko-Rado theorems for injections
- On intersecting families of independent sets in trees
- Maximum hitting of a set by compressed intersecting families
- Sharp results concerning disjoint cross-intersecting families
- A product version of the Hilton-Milner theorem
- 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)
