A short proof of a cross-intersection theorem of Hilton

Families A 1 , … , A k of sets are said to be cross-intersecting if A i ∩ A j ≠ 0̸ for any A i ∈ A i and A j ∈ A j , i ≠ j . A nice result of Hilton that generalises the Erdős–Ko–Rado (EKR) Theorem says that if r ≤ n / 2 and A 1 , … , A k are cross-intersecting sub-families of [ n ] r , then ∑ i = 1 k | A i | ≤ { n r if  k ≤ n r ; k n − 1 r − 1 if  k ≥ n r , and the bounds are best possible. We give a short proof of a slightly stronger version. For this purpose, we extend Daykin’s proof of the EKR Theorem to obtain the following improvement of the EKR Theorem: if r ≤ n / 2 , A ⊆ [ n ] r , A ∗ ≔ { A ∗ ∈ A : A ∗ ∩ A ≠ 0̸  for all  A ∈ A } and A ′ ≔ A ∖ A ∗ , then | A ∗ | + r n | A ′ | ≤ n − 1 r − 1 .