Proof of Theorem 4.2, p. 3:14 — at most N neighbourhoods and N+1 vertices force two twins across the cut
ProvedTwinWidthI.BoolWidth.exists_same_nbhdboolean-widthp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-width
Let be a finite simple graph on , let be disjoint, and let . Suppose the number of different neighbourhoods in of subsets of is at most ,
and . Then there are two distinct vertices in with the same neighbourhood in : for every , is an edge if and only if is an edge.
In the proof of Theorem 4.2 this is applied to the cut of boolean-width at most , with and ; the two vertices are the first pair to be contracted.
Formalization Note. is nbhdCount G A B, which counts neighbourhoods of all subsets of , including the empty set.
Preamble
import Mathlib import Definitions.Def_TwinWidthI_BoolWidth_Setting
Formal statement
namespace TwinWidthI.BoolWidth
open Finset
theorem exists_same_nbhd {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (A B : Finset V) (hAB : Disjoint A B) (N : ℕ)
(hcount : nbhdCount G A B ≤ N) (hA : N + 1 ≤ #A) :
∃ u ∈ A, ∃ v ∈ A, u ≠ v ∧ ∀ b ∈ B, (G.Adj u b ↔ G.Adj v b) := 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, "among the 2^k + 1 leaves of T′, corresponding to, say, A_e, two vertices u,v have the same neighborhood in B_e"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.