Bounded twin-width for polynomial expansion classes

Status open high confidence

The question of whether classes with polynomial expansion have bounded twin-width remains open as of 2026, confirmed by Bonnet's own open-problems page which lists it with the note 'we are quite far from proving it.' Twin-width IV (arXiv:2102.03117) gives a partial resolution for hereditary classes of ordered graphs, showing bounded twin-width and sub-exponential growth are equivalent in that setting. The related but strictly more general 'small conjecture' (every small class has bounded twin-width) was disproved by Twin-width VII (arXiv:2204.12330), which constructs via a Cayley-graph argument a small class with unbounded twin-width; however, that counterexample does not have polynomial expansion, so the polynomial-expansion question remains open and isolated.

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é, Rémi Watrigant · arXiv preprint · arXiv:2102.03117

  Proves that for hereditary classes of ordered graphs, bounded twin-width is equivalent to sub-exponential (2^{O(n)}) growth, giving a partial resolution of the conjecture in the ordered setting.

• partial Twin-width VII: groups (2022)
  Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé · arXiv preprint · arXiv:2204.12330

  Disproves the more general 'small conjecture' by constructing (via a finitely generated group with infinite twin-width, Theorem 1.1) a small hereditary class with unbounded twin-width (Corollary 1.4); the counterexample is not a class with polynomial expansion, so the polynomial-expansion question itself remains open.

Reviewer notes. Bonnet's open-problems page (fetched 2026-05-15) explicitly lists this question as open with the remark 'we are quite far from proving it.' The small conjecture (small ⇒ bounded twin-width) was disproved by Twin-width VII; the polynomial expansion question is a strictly harder sub-question that survives the disproof because the Cayley-graph counterexample lacks polynomial expansion.

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