Small hereditary class twin-width converse

The Small Conjecture · arXiv:2006.09877

arXiv Conjecture medium confidence— first stated 2020-06-17

Authors: Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Status disproved high confidence

The Small Conjecture ('every small hereditary class has bounded twin-width') was disproved by Bonnet, Geniet, Tessera, and Thomassé in Twin-width VII (arXiv:2204.12330, 2022), who constructed a family of induced subgraphs of an infinite Cayley graph that is small (as labeled graphs) yet has unbounded twin-width. Prior to the disproof, Twin-width IV (arXiv:2102.03117, 2021) established a positive resolution in the restricted setting of hereditary classes of ordered graphs, where bounded twin-width and smallness (growth at most 2^{O(n)}) are equivalent.

Cited literature (2)

partial Twin-width IV: ordered graphs and matrices (2021)

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé · arXiv preprint · arXiv:2102.03117

Resolves the conjecture for hereditary classes of ordered graphs by proving that bounded twin-width and growth at most 2^{O(n)} (smallness) are equivalent in this setting.
counterexample Twin-width VII: groups (2022)

Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé · arXiv preprint · arXiv:2204.12330

Disproves the conjecture by constructing a family of induced subgraphs of an infinite Cayley graph that is small as labeled graphs but has unbounded twin-width.

Reviewer notes. The general conjecture is disproved. The converse direction (every bounded twin-width class is small) was proved in the source paper and remains true. A positive analog holds for ordered graphs (Twin-width IV). The counterexample arises from group-theoretic constructions (Cayley graphs of finitely generated groups with infinite twin-width).

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Every small hereditary class has bounded twin-width.

Context

The paper proves that every bounded twin-width class is small (has at most $n! c^n$ labeled $n$-vertex graphs for some constant $c$), unifying results for bounded treewidth, proper subclasses of permutation graphs, and proper minor-closed classes. The small conjecture posits the converse. The authors explore it by verifying bounded twin-width for many natural small hereditary classes that could serve as counterexamples, including subdivisions of $K_n$, graphs of bounded stack or queue number, and cubic expanders from iterated random 2-lifts.

Notes. Explicitly named 'the small conjecture' repeatedly in the abstract and introduction; no labelled theorem environment visible in the extracted text. The PDF extraction is truncated, so later numbered conjecture environments may exist.

Source paper

Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant · 2020-06-17
https://arxiv.org/abs/2006.09877 PDF source