New injective proofs of the Erdős--Ko--Rado and Hilton--Milner theorems

2016/09/15 by Hurlbert, Glenn, Kamat, Vikram · 1 citation
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1609.04714

Abstract

A set system F is intersecting if any pair of sets in F have a nonempty intersection. A fundamental theorem of Erdő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 Erdős--Ko--Rado and the Hilton--Milner theorems.

Cited by

• Hilton-Milner Theorem for the r-independent sets in a union of cliques

Related

• Short injective proofs of the Erdős-Ko-Rado and Hilton-Milner Theorem: A canonical partition of shifted intersecting set systems
• A degree version of the Hilton--Milner theorem
• The structure of large intersecting families
• A Common Generalization of the Theorems of Erdős-Ko-Rado and Hilton-Milner
• Erdős-Ko-Rado theorem and Hilton-Milner type theorem for k-partitions