A set system F is intersecting if any pair of sets in F have a nonempty intersection. A fundamental theorem of Erd\H{ 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 Erd\H{ o}s--Ko--Rado and the Hilton--Milner theorems.
Categories: math.CO