Theorem 4.2 — every graph with boolean-width k has twin-width at most 2^{k+1} − 1
ProvedTwinWidthI.BoolWidth.theorem_4_2Theorem 4.2. Every graph with boolean-width has twin-width at most .
Precisely: let be a finite simple graph and an integer such that has a decomposition tree in which every edge induces a cut with at most different neighbourhoods in of subsets of . Then
For , the least such count when , this is .
Since , the theorem shows that classes of bounded boolean-width, clique-width or rank-width have bounded twin-width.
Formalization Note. Boolean-width is kept as the integer count (BoolWidthLE G N) rather than its base-2 logarithm, and twin-width as the predicate TwinWidthLE G d. Since means that the least with BoolWidthLE G N is (an integer, being a count, although itself need not be), and then , the statement is exactly Theorem 4.2; for larger it follows from the case of the least because TwinWidthLE is monotone in its bound. The subtraction is in ; for the hypothesis forces (a graph with two or more vertices has a cut with at least one neighbourhood), where twin-width is correct. A graph on the empty vertex set has no decomposition tree, so the statement says nothing about it.
import Mathlib import Definitions.Def_TwinWidthI_BoolWidth_Setting
namespace TwinWidthI.BoolWidth
open Finset
theorem theorem_4_2 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (N : ℕ) (hN : BoolWidthLE G N) : TwinWidthLE G (2 * N - 1) := by sorry
end TwinWidthI.BoolWidth
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.