New injective proofs of the Erdos-Ko-Rado and Hilton-Milner theorems

摘要

A set system F is intersecting if for any F, F' epsilon F boolean AND F' not equal (sic). A fundamental theorem of Erdos, Ko and Rado states that if F is an intersecting family of r-subsets of [n] = {1, ..., n}, and n = 2r, then vertical bar F vertical bar = ((n-1)(r-1)). Furthermore, when n 2r, equality holds if and only F is the family of all r-subsets of [n] containing a fixed element. This was proved as part of a stronger result by Hilton and Milner. In this note, we provide new injective proofs of the Erdos-Ko-Rado and the Hilton-Milner theorems. (C) 2018 Elsevier B.V. All rights reserved.