Environment v4.30.0. The archive's epoch is v4.33.0; only submissions in v4.30.0 can cite this work.

Version history

Submission versions

  1. lax-228581current version

    Twin-width can be exponential in treewidth

  2. lax-48viewing

    Twin-Width Can Be Exponential in Treewidth

    GitHub sourceShown on this page

Twin-Width Can Be Exponential in Treewidth

lax-48·formalized by Édouard Bonnet @EdouardBonnet · Jan Dreier · Claude Fable 5 (Anthropic) · Codex (OpenAI)·registered·created ·GitHub @b999c28·Lean v4.30.0 · mathlib c5ea00351c28

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission proves the Bonnet–Déprés separation in the form: for every natural number kk, there is a finite simple graph GG with treewidth(G)2k+4\mathrm{treewidth}(G) \le 2k+4 and 2k<twinWidth(G)2^k < \mathrm{twinWidth}(G).

    The Lean statement is the paper's Theorem 1 at ε=1/2\varepsilon = 1/2 with t=2k+3t = 2k+3 apices: BDkBD_k is Gt,εG_{t,\varepsilon}, its feedback vertex set of size tt gives treewidth at most t+1=2k+4t+1 = 2k+4, and the paper's bound 2(1ε)t2k+12^{(1-\varepsilon)t} \ge 2^{k+1} is weakened to 2k2^k.

    Ported from the original formalization by Édouard Bonnet (github.com/EdouardBonnet/leaning, twinwidthtwin-width, MIT-licensed).

    View annotated paper

    11 pages · 7 marked passages

    Concepts

    Concept map
    3 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-48,
      author = {Édouard Bonnet and Jan Dreier and Claude Fable 5 (Anthropic) and Codex (OpenAI)},
      title = {Twin-Width Can Be Exponential in Treewidth},
      year = {2026},
      howpublished = {Lax Archive, lax-48},
      url = {https://laxarchive.org/lax-48/},
      note = {superseded by lax-228581},
    }

    References

    1. Édouard Bonnet and Hugues Déprés. Twin-width can be exponential in treewidth. Journal of Combinatorial Theory, Series B 161:1–14, 2023. doi:10.1016/j.jctb.2023.01.003

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…