Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas

Abstract

A family A of sets is said to be intersecting if every two sets in A intersect. Two families A and B are said to be cross-intersecting if each set in A intersects each set in B. For a positive integer n, let [n] = {1, . . . , n} and Sn = {A ⊆ [n] : 1 ∈ A}. We extend the Erdős–Ko–Rado Theorem by showing that if A and B are non-empty cross-intersecting families of subsets of [n], A is intersecting, and a0, a1, . . . , an, b0, b1, . . . , bn are non-negative real numbers such that ai + bi ≥ an−i + bn−i and an−i ≥ bi for each i ≤ n/2, then Σ A∈A a|A| + Σ B∈B b|B| ≤ Σ A∈Sn a|A| + Σ B∈Sn b|B|. For a graph G and an integer r ≥ 1, let IG (r) denote the family of r-element independent sets of G. Inspired by a problem of Holroyd and Talbot, Feghali, Johnson and Thomas conjectured that if r < n and G is a depth-two claw with n leaves, then G has a vertex v such that {A ∈ IG (r) : v ∈ A} is a largest intersecting subfamily of IG (r). They proved this for r ≤ n+1/ 2 . We use the result above to prove the full conjecture.