Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5, p. 3:15 — subgraphs of unit ddd-dimensional ball graphs with clique number kkk have twin-width at most (3⌈d⌉)dk(3\lceil\sqrt d\rceil)^d k(3⌈d​⌉)dk

Proved
TwinWidthI.BallGraph.theorem_4_5

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

geometric-intersection-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-widthunit-ball-graph

Let d,k≥0d,k\ge 0d,k≥0, let VVV be a finite set and c:V→Rdc:V\to\mathbb R^dc:V→Rd, and let GGG be the unit ddd-dimensional ball graph with centres ccc: distinct u,v∈Vu,v\in Vu,v∈V are adjacent iff the closed unit balls around c(u)c(u)c(u) and c(v)c(v)c(v) meet, i.e. ∥c(u)−c(v)∥2≤2\|c(u)-c(v)\|_2\le 2∥c(u)−c(v)∥2​≤2. Suppose GGG has clique number at most kkk. Then every subgraph HHH of GGG (on a vertex set S⊆VS\subseteq VS⊆V, with every edge of HHH an edge of GGG) satisfies

tww⁡(H)≤d′:=(3⌈d ⌉)d k.\operatorname{tww}(H)\le d':=(3\lceil\sqrt d\,\rceil)^d\,k .tww(H)≤d′:=(3⌈d​⌉)dk.

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 kkk" is encoded as "no clique of size k+1k+1k+1" (CliqueFree (k+1)), i.e. clique number at most kkk; this is the same theorem since the bound is monotone in kkk. "Subgraph" allows deleting vertices (the finite set SSS) and edges (H≤G[S]H\le G[S]H≤G[S]). ⌈d ⌉\lceil\sqrt d\,\rceil⌈d​⌉ is the natural-number ceiling of the real square root, so d′d'd′ is a natural number. Twin-width is the partition-form predicate TwinWidthLE of the Setting. The second sentence of the theorem (a d′d'd′-contraction sequence can be found in polynomial time from a geometric representation) is about running time and is not formalized.

Preamble
import Mathlib
import Definitions.Def_TwinWidthI_BallGraph_Setting
Formal statement
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
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:15, Theorem 4.5 (first sentence); proof p. 3:16
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me