Environment v4.30.0. The archive's epoch is v4.33.0; only submissions in v4.30.0 can cite this work.
Twin-Width Can Be Exponential in Treewidth
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This submission proves the Bonnet–Déprés separation in the form: for every natural number , there is a finite simple graph with and .
The Lean statement is the paper's Theorem 1 at with apices: is , its feedback vertex set of size gives treewidth at most , and the paper's bound is weakened to .
Ported from the original formalization by Édouard Bonnet (github.com/EdouardBonnet/leaning, , MIT-licensed).
11 pages · 7 marked passages
Concepts
Concept map
Proofs
Proof networkview on GitHub
Proof list
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
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
- É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.
0 comments