Proof of Theorem 4.2, p. 3:14 — contracting two twins across the cut gives a (2N − 1)-partition
ProvedTwinWidthI.BoolWidth.first_contraction_red_degreeboolean-widthp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-width
Let be a finite simple graph on , let be a partition of (that is, and ), and let with . Let be two vertices of with the same neighbourhood in . Let be the partition of whose parts are and the singletons , (the partition after contracting and ). Then is a -partition: every part of is non-homogeneous to at most
other parts.
With this is the paper's claim that after the first contraction all red edges lie within , so the red degree is at most .
Formalization Note. The contracted graph is represented by the partition (partition form of twin-width); the hypothesis hP fixes its parts. The subtraction is in ; it is exact whenever the hypotheses hold, since forces .
Preamble
import Mathlib import Definitions.Def_TwinWidthI_BoolWidth_Setting
Formal statement
namespace TwinWidthI.BoolWidth
open Finset
theorem first_contraction_red_degree {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (A B : Finset V) (hAB : Disjoint A B) (hcover : A ∪ B = univ)
(N : ℕ) (hA : #A ≤ 2 * N) (u v : V) (hu : u ∈ A) (hv : v ∈ A) (huv : u ≠ v)
(htwin : ∀ b ∈ B, (G.Adj u b ↔ G.Adj v b))
(P : Finpartition (univ : Finset V))
(hP : P.parts = insert {u, v} (((univ.erase u).erase v).image fun w => ({w} : Finset V))) :
IsDPartition G P (2 * N - 1) := by sorry
end TwinWidthI.BoolWidth
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:14, proof of Theorem 4.2, "The only red edges in G/u,v are within A_e, so the red degree is bounded by 2^{k+1} − 1"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.