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

作者：Hurlbert Glenn; Kamat Vikram^*

来源：Discrete Mathematics, 2018, 341(6): 1749-1754.

DOI：10.1016/j.disc.2018.03.010

• 05D05
• Intersecting families
• Erdos-Ko-Rado
• Hilton-Milner
• Shifting technique
• Injective proof

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.

• 出版日期2018-6