Proof of Lemma 2.2, p. 3 — if non-adjacent vertices of share neighbourhoods and is -free, is complete -partite
ProvedTuranMatching.Clique.induced_complete_k_partitecomplete-multipartiteextremal-graph-theorymatching-numberp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1turan-number
Let , let be a graph on vertices with no clique on vertices, and let be a set of vertices such that every two non-adjacent vertices of have the same neighbourhood in . Then the induced subgraph is complete -partite: there is a map from the vertices to such that for all ,
Some of the classes may be empty, as the paper allows. This is the first step of the proof of Lemma 2.2.
Formalization Note The classes are encoded by a map into Fin k; its values outside are irrelevant. The hypothesis is the standing restriction of the formalization (some is needed for a map into to exist).
Preamble
import Mathlib import Definitions.Def_TuranMatching_Clique_Setting open Finset SimpleGraph
Formal statement
namespace TuranMatching.Clique
theorem induced_complete_k_partite (n k : ℕ) (hk : 2 ≤ k)
(G : SimpleGraph (Fin n)) (hK : G.CliqueFree (k + 1)) (B : Finset (Fin n))
(hsame : ∀ u ∈ B, ∀ v ∈ B, ¬ G.Adj u v → G.neighborSet u = G.neighborSet v) :
∃ cls : Fin n → Fin k, ∀ u ∈ B, ∀ v ∈ B, G.Adj u v ↔ cls u ≠ cls v := by sorry
end TuranMatching.Clique
Source
Alon and Frankl, Turán graphs with bounded matching number, arXiv:2210.15076v1, p. 3, proof of Lemma 2.2, first two sentences
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.