Theorem 1.1 (Erdős) — for large n, no t+1 pairwise disjoint k-sets implies |F| ≤ C(n,k) − C(n−t,k), with the star family unique
ProvedLinearPathTuran.Exact.theorem_1_1erdos-matchingextremal-set-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Erdős' matching theorem for large . Let be positive integers. There is such that for every : if contains no pairwise disjoint members, then
and equality holds only for the family of all -subsets of meeting some fixed set of elements.
In the paper it bounds, in equation (5), the -uniform link families that arise near the exceptional set.
Formalization Note is an existential threshold chosen after . The equality clause is an equivalence: a family under the hypotheses has exactly members iff it is the star family of some -set. The subtraction is exact in . The theorem is cited from Erdős (1965).
Preamble
import Mathlib import Definitions.Def_LinearPathTuran_Exact_Setting
Formal statement
namespace LinearPathTuran.Exact
open Finset
/-- Theorem 1.1 (Erdős 1965), p. 2: for large `n`, a `k`-uniform family on `[n]` with no `t + 1`
pairwise disjoint members has at most `C(n, k) - C(n - t, k)` members, with equality only for the
family of all `k`-sets meeting a fixed `t`-set. -/
theorem theorem_1_1 (k t : ℕ) (hk : 1 ≤ k) (ht : 1 ≤ t) :
∃ n₀ : ℕ, ∀ n > n₀, ∀ 𝓕 : Finset (Finset (Fin n)),
𝓕 ⊆ (univ : Finset (Fin n)).powersetCard k →
(¬ ∃ 𝓜 ⊆ 𝓕, #𝓜 = t + 1 ∧ (𝓜 : Set (Finset (Fin n))).PairwiseDisjoint id) →
#𝓕 ≤ n.choose k - (n - t).choose k ∧
(#𝓕 = n.choose k - (n - t).choose k ↔
∃ S : Finset (Fin n), #S = t ∧ 𝓕 = starFamily n k S) := by sorry
end LinearPathTuran.Exact
Source
Füredi, Jiang and Seiver, Exact solution of the hypergraph Turán problem for k-uniform linear paths, arXiv:1108.1247v1, p. 2, Theorem 1.1 (cited from Erdős, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8 (1965))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.