New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
From MaRDI portal
(Redirected from 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
- A new short proof of the EKR theorem
- A simple proof of the Erdős-Chao Ko-Rado theorem
- Erdős-Ko-Rado from Kruskal-Katona
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Erdős-Ko-Rado theorems. Algebraic approaches
- Erdös–Ko–Rado Theorem—22 Years Later
- Extremal t -intersecting sub-families of hereditary families
- 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?)
- 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 best possible inequalities concerning cross-intersecting families
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Strongly intersecting integer partitions
Cited in
(23)- 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
- On strengthenings of the intersecting shadow theorem
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- On intersecting families of independent sets in trees
- Cross-intersecting subfamilies of levels of hereditary families
- Non-trivial \(d\)-wise intersecting families
- A simple proof of the Hilton-Milner theorem
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
- Intersecting families, signed sets, and injection
- A product version of the Hilton-Milner theorem
- Improved bounds on the maximum diversity of intersecting families
- Maximum hitting of a set by compressed intersecting families
- The maximum of the product of nontrivial cross-intersecting 3-graphs
- A Hilton-Milner theorem for exterior algebras
- Maximal intersecting families revisited
- A result for hemi-bundled cross-intersecting families
- Strict Erdős-Ko-Rado for simplicial complexes (extended abstract)
- A short proof of the Hilton-Milner theorem
- Some Erdős-Ko-Rado theorems for injections
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)
