§2, p. 4, Case 4 — is non-decreasing in with steps at most
ProvedTuranMatching.Clique.turan_incrementextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-number
Let and , and write . Then
- , the total size of the largest classes of ;
- ;
- .
Equivalently, when the number of vertices decreases by one, can only decrease, and by at most :
This is the fact behind the discrete convexity of in Case 4.
Formalization Note The differences are computed in ℤ; is natural division. The statement holds for every ; the paper uses it for .
Preamble
import Mathlib import Definitions.Def_TuranMatching_Clique_Setting open Finset SimpleGraph
Formal statement
namespace TuranMatching.Clique
theorem turan_increment (k : ℕ) (hk : 1 ≤ k) (N : ℕ) :
((turanNum (N + 1) k : ℤ) - turanNum N k = (N : ℤ) - (N / k : ℕ)) ∧
((turanNum (N + 1) k : ℤ) - turanNum N k ≤ (turanNum (N + 2) k : ℤ) - turanNum (N + 1) k) ∧
((turanNum (N + 2) k : ℤ) - turanNum (N + 1) k ≤ (turanNum (N + 1) k : ℤ) - turanNum N k + 1) := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 4, Case 4 ("When b increases by 1, … by at most 1 …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.