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
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
@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/},
}
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
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments