Proposition 3.4 (the rank bound) — a (k,s)-homogeneous family whose pattern has rank p has at most C(n,p) members
ProvedLinearPathTuran.Exact.proposition_3_4delta-systemextremal-set-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
The rank bound. Let be positive integers and let be a -homogeneous family on vertices with intersection pattern . If , then
This is why only homogeneous pieces whose pattern has rank or can carry members; pieces of rank at most contribute .
Formalization Note The rank is the minimum size of a subset of contained in no member of ; since the members of are proper subsets of this minimum exists.
Preamble
import Mathlib import Definitions.Def_LinearPathTuran_Exact_DeltaSystem
Formal statement
namespace LinearPathTuran.Exact
open Finset
/-- Proposition 3.4 (the rank bound), p. 5. -/
theorem proposition_3_4 (k s : ℕ) (hk : 1 ≤ k) (hs : 1 ≤ s) {n : ℕ}
(𝓕 : Finset (Finset (Fin n))) (χ : Fin n → Fin k) (J : Finset (Finset (Fin k)))
(hH : IsHomogeneous s 𝓕 χ J) (p : ℕ) (hp : rank J = p) :
#𝓕 ≤ n.choose p := 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. 5, Proposition 3.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.