Erdős–Ko–Rado for d-cluster-free families

Definition\(K(d)\)-families#✓fully proved

Let \(n\), \(k\) and \(d\) be natural numbers and let \([n] = \{0, 1, \dots, n - 1\}\). A family \(G\) of subsets of \([n]\) is a \(K(d)\)-family of \(k\)-subsets when every member of \(G\) has exactly \(k\) elements and any \(d\) distinct members \(A_1, \dots, A_d\) of \(G\) with \(|A_1 \cup \dots \cup A_d| \le 2k\) have a common element.

def IsKdFamily (n k d : ℕ) (G : Finset (Finset (Fin n))) : Prop :=
  (∀ A ∈ G, A.card = k) ∧
    ∀ A : Fin d → Finset (Fin n), Function.Injective A → (∀ i, A i ∈ G) →
      (Finset.univ.biUnion A).card ≤ 2 * k → ∃ x, ∀ i, x ∈ A i

Used by 1

Used byMubayi's Erdős–Ko–Rado conjecture for \(K(d)\)-families

DefinitionMubayi's Erdős–Ko–Rado conjecture for \(K(d)\)-families#✓fully proved

For all natural numbers \(n\), \(k\) and \(d\) with \(3 \le d \le k\) and \(n \ge dk/(d - 1)\), every \(K(d)\)-family \(G\) of \(k\)-subsets of \([n] = \{0, 1, \dots, n - 1\}\) satisfies \(|G| \le \binom{n-1}{k-1}\), and if \(|G| = \binom{n-1}{k-1}\) then some element of \([n]\) lies in every member of \(G\).

def kdFamilyErdosKoRado : Prop :=
  ∀ n k d : ℕ, 3 ≤ d → d ≤ k → (d : ℝ) * k / (d - 1) ≤ n →
    ∀ G : Finset (Finset (Fin n)), IsKdFamily n k d G →
      G.card ≤ (n - 1).choose (k - 1) ∧
        (G.card = (n - 1).choose (k - 1) → ∃ x, ∀ A ∈ G, x ∈ A)

Sources

• D. Mubayi, Oberwolfach Report 48/2006, Conjecture 3.

Uses 1 · Used by 1

Statement uses\(K(d)\)-families

Used byMubayi's Erdős–Ko–Rado conjecture for \(K(d)\)-families holds

TheoremMubayi's Erdős–Ko–Rado conjecture for \(K(d)\)-families holds#●ready to prove

For all natural numbers \(n\), \(k\) and \(d\) with \(3 \le d \le k\) and \(n \ge dk/(d - 1)\), every \(K(d)\)-family \(G\) of \(k\)-subsets of \([n] = \{0, 1, \dots, n - 1\}\) satisfies \(|G| \le \binom{n-1}{k-1}\), and if \(|G| = \binom{n-1}{k-1}\) then some element of \([n]\) lies in every member of \(G\).

Currier proved the bound for \(2 \le d \le k\), with the equality case for \(d \ge 3\).

public theorem_wanted kdFamilyErdosKoRado_holds : kdFamilyErdosKoRado

Sources

• D. Mubayi, in Combinatorics, Probability and Computing, Oberwolfach Reports 3 (2006), no. 48, p. 2922, Conjecture 3, DOI 10.4171/OWR/2006/48; resolution: G. Currier, On the d-cluster generalization of Erdős-Ko-Rado, J. Combin. Theory Ser. A 182 (2021), 105464, arXiv:1812.11153, abstract and Theorem 2: for 2 ≤ d ≤ k and n ≥ dk/(d - 1), a family of k-subsets of [n] with no d-cluster (d members with empty intersection and union of size at most 2k) has at most C(n - 1, k - 1) members, with equality only for a full star (d ≥ 3); this resolves Mubayi's conjecture, https://arxiv.org/abs/1812.11153.

Uses 1

Statement usesMubayi's Erdős–Ko–Rado conjecture for \(K(d)\)-families

2 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.