Erdős-Ko-Rado with separation conditions

Abstract

A family A of sets is said to be intersecting if A ∩ B≠θ for every A,B A. For a family F of sets, let ex(F):= {A ⊆ F: A is a largest intersecting subfamily of F}. For n ≥ 0 and r ≥ 0, let [n]:= {i ∈ N: i ≤ n} = {A ⊆ [n]: |A| = r}. For a sequence {di}i∈ℕ of non-negative integers that is monotonically non-decreasing (i.e. di ≤ di+1 for all i ∈ ℕ), let P({di}i∈ℕ):= {{a1,t, ar} ⊂ ℕ: r ∈ ℕ, ai+1 gt; ai + dai for each i ∈ [r-1]}. Let P(r)n:= P({di}i∈ℕ) We determine ex(P(r)n) for d1 gt; 0 and any r, and for d1 = 0 and r ≤ 1/2 max{s ∈ [n]: P(s)n ≠ θ}. We particularly have that {A ∈ P(r)n: 1 ∈ A} ∈ ex(P(r)n); Holroyd, Spencer and Talbot established this for the case where d1 gt; 0 and di = d1 for all i ∈ℕ, and a part of the paper generalises a compression method that they introduced. The Erdo{double acute}s-Ko-Rado Theorem and the Hilton-Milner Theorem provide the solution for the case where di = 0 for all i ∈ℕ.