Theorem 4.5, p. 3:15 — subgraphs of unit -dimensional ball graphs with clique number have twin-width at most
ProvedTwinWidthI.BallGraph.theorem_4_5Let , let be a finite set and , and let be the unit -dimensional ball graph with centres : distinct are adjacent iff the closed unit balls around and meet, i.e. . Suppose has clique number at most . Then every subgraph of (on a vertex set , with every edge of an edge of ) satisfies
Unit disk graphs without a bound on the clique number have unbounded twin-width (p. 3:16), so the clique-number bound is what makes the class tractable; with the paper's main theorem this gives FPT first-order model checking on these graphs, given a contraction sequence.
Formalization Note. "Clique number " is encoded as "no clique of size " (CliqueFree (k+1)), i.e. clique number at most ; this is the same theorem since the bound is monotone in . "Subgraph" allows deleting vertices (the finite set ) and edges (). is the natural-number ceiling of the real square root, so is a natural number. Twin-width is the partition-form predicate TwinWidthLE of the Setting. The second sentence of the theorem (a -contraction sequence can be found in polynomial time from a geometric representation) is about running time and is not formalized.
import Mathlib import Definitions.Def_TwinWidthI_BallGraph_Setting
namespace TwinWidthI.BallGraph
/-- Theorem 4.5, p. 3:15: every subgraph `H` of a unit d-dimensional ball graph `G` with clique
number (at most) `k` has twin-width at most `(3⌈√d⌉)^d k`. -/
theorem theorem_4_5 (d k : ℕ) {V : Type*} [Fintype V] [DecidableEq V]
(c : V → EuclideanSpace ℝ (Fin d)) (hK : (ballGraph c).CliqueFree (k + 1))
(S : Finset V) (H : SimpleGraph S) (hH : H ≤ (ballGraph c).induce (S : Set V)) :
TwinWidthI.BoolWidth.TwinWidthLE H ((3 * ⌈Real.sqrt d⌉₊) ^ d * k) := by sorry
end TwinWidthI.BallGraph
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.