§2, p. 4, Case 2 —
ProvedTuranMatching.Clique.case_2_identityextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-number
Let , write , and let . Then
This is the "exactly" of Case 2: the Turán graph on the vertices of the small classes together with vertices of the large class, plus the remaining vertices each joined to the small-class vertices, is .
Formalization Note is natural-number division; is natural subtraction, exact under . is the edge count of the graph , so the identity is a genuine statement about that graph. The paper says "every "; the restriction is needed because has classes of total size , which is impossible for and , and no graph on vertices has clique number at most .
Preamble
import Mathlib import Definitions.Def_TuranMatching_Clique_Setting open Finset SimpleGraph
Formal statement
namespace TuranMatching.Clique
theorem case_2_identity (n k s : ℕ) (hk : 2 ≤ k) (hn : s + s / (k - 1) ≤ n) :
turanNum (s + s / (k - 1)) k + (n - s - s / (k - 1)) * s = gNum n k s := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 4, Case 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.