§2, p. 4, Case 4 — has strictly increasing differences
ProvedTuranMatching.Clique.f_discrete_convexextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-number
Let , , and
For every with (so that , and all lie in the range of Case 4),
So is discretely convex on the range of Case 4, and its maximum over that range is attained at an endpoint.
Formalization Note is integer-valued (fCase4), with a natural subtraction that is exact on the range. "Increasing" is taken strictly, as the linear part grows by and the Turán bracket shrinks by at most . 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 f_discrete_convex (n k s b : ℕ) (hk : 2 ≤ k) (hn : 2 * s + 1 ≤ n)
(hb : b + 2 ≤ s - s / (k - 1)) :
fCase4 n k s (b + 1) - fCase4 n k s b < fCase4 n k s (b + 2) - fCase4 n k s (b + 1) := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 4, Case 4 (definition of f and "f(b + 1) − f(b) is an increasing function of b")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.