p. 1, Theorem 1.1 (lower bound); p. 5 — and plus isolated vertices are admissible
ProvedTuranMatching.Clique.extremal_graphs_admissibleextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-number
Let , and . Then:
- the graph has clique number at most and matching number at most ;
- there is a graph on vertices with clique number at most and matching number at most that has exactly edges.
Hence
is a lower bound for the maximum number of edges of an -vertex graph with clique number at most and matching number at most . This is the lower-bound half of Theorem 1.1; the natural witness for (2) is the Turán graph on of the vertices with the remaining vertices isolated.
Formalization Note 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 extremal_graphs_admissible (n k s : ℕ) (hk : 2 ≤ k) (hn : 2 * s + 1 ≤ n) :
Admissible k s (bigGraph n k s) ∧
∃ (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj), Admissible k s G ∧
#G.edgeFinset = turanNum (2 * s + 1) k := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 1, Theorem 1.1 (the lower bound); p. 5, proof of Proposition 3.1, first two sentences
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.