pith. sign in

arxiv: 2606.21640 · v1 · pith:OX65742Wnew · submitted 2026-06-19 · 🧮 math.CO · cs.DM

The Twin-Width of Graphs of Bounded VC-Dimension

Therese Biedl , Taite LaGrange , Sophie Spirkl This is my paper

Pith reviewed 2026-06-26 13:29 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords twin-widthVC-dimensionhereditary classessub-linear boundsinterval graphscontraction sequencesinduced subgraphsneighbourhood partitions
0
0 comments X

The pith

Graphs with bounded VC-dimension have twin-width at most sub-linear in the number of vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines which hereditary graph classes admit sub-linear bounds on twin-width. It first constructs examples showing that split graphs, bipartite graphs, and co-bipartite graphs can all have linear twin-width. Bounded VC-dimension is equivalent to excluding one induced subgraph from each of those three families. A general tool is introduced that produces twin-width upper bounds by contracting according to a partition into vertices with distinct neighbourhoods. Applying the tool shows that bounded VC-dimension forces twin-width to be sub-linear rather than linear, with a separate tighter bound derived for interval graphs.

Core claim

Modifying conference graphs produces split, bipartite, and co-bipartite examples with linear twin-width. Because bounded VC-dimension is equivalent to forbidding an induced subgraph from each of these three families, the question arises whether twin-width can still be linear under bounded VC-dimension. A contraction tool is presented that obtains twin-width bounds by partitioning vertices according to distinct neighbourhoods and contracting within each part. This tool is applied to prove that graphs of bounded VC-dimension have twin-width at most sub-linear in the number of vertices. A tighter upper bound is obtained for interval graphs together with a lower bound.

What carries the argument

The contraction tool obtained by partitioning vertices according to distinct neighbourhoods, which contracts each part to produce an upper bound on twin-width.

If this is right

  • Split graphs, bipartite graphs, and co-bipartite graphs can have linear twin-width.
  • Graphs with bounded VC-dimension have sub-linear twin-width.
  • Interval graphs admit a tighter upper bound on twin-width than the general sub-linear result.
  • A lower bound on twin-width holds for some graphs of bounded VC-dimension.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The neighbourhood-partition contraction may extend to bound twin-width in other hereditary classes defined by forbidden induced subgraphs.
  • The separation between linear and sub-linear twin-width tracks precisely with the presence or absence of bounded VC-dimension.
  • Further application of the same tool could produce explicit constants or tighter growth rates inside particular bounded-VC-dimension families.

Load-bearing premise

The contraction tool obtained by partitioning vertices according to distinct neighbourhoods yields valid upper bounds on twin-width.

What would settle it

A family of graphs with bounded VC-dimension whose twin-width grows linearly with the number of vertices would falsify the sub-linear upper bound.

Figures

Figures reproduced from arXiv: 2606.21640 by Sophie Spirkl, Taite LaGrange, Therese Biedl.

Figure 1
Figure 1. Figure 1: The constructed graph for Theorem 5.2; here [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
read the original abstract

In this paper, we investigate which hereditary classes of graphs admit sub-linear (in the number of vertices) bounds on twin-width. By modifying conference graphs, we can show that split, bipartite, and co-bipartite graphs can all have linear twin-width. However, excluding an induced subgraph of each of these three types is equivalent to the class of graphs having bounded VC-dimension, as shown by Bousquet, Lagoutte, Li, Parreau and Thomass\'e. Graphs of bounded VC-dimension can have unbounded twin-width, but whether it can be linear was an open question. In this paper, we first present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. Then, using this tool, we prove that graphs with bounded VC-dimension have twin-width at most sub-linear. We also obtain a separate, tighter upper bound for the class of interval graphs, as well as a lower bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper shows that split, bipartite, and co-bipartite graphs can have linear twin-width via modifications of conference graphs. It recalls that bounded VC-dimension is equivalent to excluding one induced subgraph from each of these three families. While graphs of bounded VC-dimension can have unbounded twin-width, whether the twin-width can be linear remained open. The authors introduce a general contraction tool that obtains twin-width upper bounds by partitioning vertices according to distinct neighbourhoods and contracting each part; they apply the tool to prove that bounded VC-dimension implies sub-linear twin-width. Separate tighter upper and lower bounds are given for interval graphs.

Significance. If the contraction tool is shown to produce valid sequences whose red-degree is controlled by the number of distinct neighbourhoods, the result resolves the open question by establishing a sub-linear (rather than merely unbounded or linear) upper bound on twin-width for all hereditary classes of bounded VC-dimension. The tool itself, if correctly verified, supplies a reusable method for deriving twin-width bounds from neighbourhood diversity and could be applied to other hereditary classes. The connection to the Sauer-Shelah lemma is a natural strength.

major comments (2)
  1. [Section presenting the contraction tool] The central claim rests on the neighbourhood-partition contraction tool. The manuscript asserts that contracting according to a partition into sets of identical neighbourhoods yields a valid twin-width upper bound, yet supplies no explicit argument that the maximum red degree after contraction is bounded by a function of the number of distinct neighbourhoods, nor that repeated applications on the contracted graph preserve this control without the red degree blowing up. This verification is load-bearing for the sub-linear conclusion.
  2. [Proof applying the tool to VC-dimension-bounded graphs] In the proof that bounded VC-dimension implies sub-linear twin-width, the application of the tool is said to rely on the Sauer-Shelah lemma to bound the number of distinct neighbourhoods. However, without a concrete check that each contraction step keeps the red degree within the claimed function of that number, it is impossible to confirm that the overall bound remains sub-linear rather than reverting to linear or worse.
minor comments (2)
  1. The construction that produces linear twin-width examples for split, bipartite, and co-bipartite graphs via modified conference graphs is only sketched; a short explicit description or reference to the precise modification would improve readability.
  2. Notation for the red-degree function and the precise definition of the contraction sequence could be stated once at the beginning of the tool section to avoid repeated implicit appeals to the twin-width definition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments correctly identify that the verification of the neighbourhood-partition contraction tool needs to be made fully explicit. We will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Section presenting the contraction tool] The central claim rests on the neighbourhood-partition contraction tool. The manuscript asserts that contracting according to a partition into sets of identical neighbourhoods yields a valid twin-width upper bound, yet supplies no explicit argument that the maximum red degree after contraction is bounded by a function of the number of distinct neighbourhoods, nor that repeated applications on the contracted graph preserve this control without the red degree blowing up. This verification is load-bearing for the sub-linear conclusion.

    Authors: We agree that an explicit, self-contained argument for the red-degree bound is required. In the revised version we will insert a new lemma immediately after the definition of the tool. The lemma will prove that, when a graph is contracted by partitioning vertices into sets of identical neighbourhoods, the red degree in the resulting trigraph is at most one less than the number of parts; it will also contain an inductive argument showing that the same bound applies after any number of subsequent contractions performed on the contracted graph, because each contraction step can only decrease (or leave unchanged) the number of distinct neighbourhoods relative to the original vertex set. This will directly address the concern that the red degree might blow up under iteration. revision: yes

  2. Referee: [Proof applying the tool to VC-dimension-bounded graphs] In the proof that bounded VC-dimension implies sub-linear twin-width, the application of the tool is said to rely on the Sauer-Shelah lemma to bound the number of distinct neighbourhoods. However, without a concrete check that each contraction step keeps the red degree within the claimed function of that number, it is impossible to confirm that the overall bound remains sub-linear rather than reverting to linear or worse.

    Authors: The current proof invokes the Sauer-Shelah lemma to bound the number of distinct neighbourhoods at the outset and then applies the contraction tool repeatedly. We concede that the manuscript does not explicitly track how the red-degree function evolves across iterations. In the revision we will add a short paragraph (or a dedicated claim inside the proof) that combines the new lemma with the Sauer-Shelah bound: at every step the red degree is bounded by a function of the current number of distinct neighbourhoods, which itself is at most O(n^{1-ε}) for some ε>0 depending only on the VC-dimension; the resulting recurrence yields an overall sub-linear upper bound on twin-width. This will make the sub-linearity fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity: new contraction tool applied to VC-dimension bound

full rationale

The paper introduces a contraction tool based on partitioning vertices by identical neighbourhoods and applies it to derive a sub-linear twin-width bound for bounded VC-dimension classes. This relies on the Sauer-Shelah lemma for the number of distinct neighbourhoods and an external citation to Bousquet et al. for the hereditary class characterization. No step reduces the claimed upper bound to a fitted parameter, self-citation chain, or definitional equivalence; the tool is presented as a new general construction whose validity is asserted independently of the target VC-dimension result. The derivation chain remains self-contained against external combinatorial facts.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on a prior equivalence result (bounded VC-dimension iff excluding induced subgraphs from split/bipartite/co-bipartite classes) cited from Bousquet et al., plus the correctness of the new contraction tool whose details are not visible in the abstract.

axioms (1)
  • domain assumption Bounded VC-dimension is equivalent to excluding an induced subgraph from each of split, bipartite, and co-bipartite graphs (Bousquet et al.)
    Invoked to reduce the problem to the three classes that can have linear twin-width.

pith-pipeline@v0.9.1-grok · 5698 in / 1186 out tokens · 23262 ms · 2026-06-26T13:29:53.604802+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 22 canonical work pages

  1. [1]

    Twin-width of random graphs,

    J. Ahn, D. Chakraborti, K. Hendrey, D. Kim, and S.-i. Oum, “Twin-width of random graphs,”Random Struct. Alg., vol. 65, no. 4, pp. 794–831, Jun. 2024.doi:10.1002/ rsa.21247arXiv:2212.07880. [Online]. Available:http://dx.doi.org/10.1002/ rsa.21247

    arXiv 2024

  2. [2]

    Bounds for the twin-width of graphs,

    J. Ahn, K. Hendrey, D. Kim, and S.-i. Oum, “Bounds for the twin-width of graphs,” SIAM Journal on Discrete Mathematics, vol. 36, no. 3, pp. 2352–2366, Sep. 2022. doi:10 . 1137 / 21m1452834[Online]. Available:http : / / dx . doi . org / 10 . 1137 / 21M1452834

    2022

  3. [3]

    Twin-width one,

    J. Ahn, H. Jacob, N. K¨ ohler, C. Paul, A. Reinald, and S. Wiederrecht, “Twin-width one,”CoRR, Jan. 2025. arXiv:2501.00991. [Online]. Available:http://arxiv.org/ abs/2501.00991

    arXiv 2025

  4. [4]

    The micro-world of cographs,

    B. Alecu, V. Lozin, and D. de Werra, “The micro-world of cographs,”Discrete Applied Mathematics, vol. 312, 2022.doi:10.1016/j.dam.2021.11.004

    work page doi:10.1016/j.dam.2021.11.004 2022

  5. [5]

    On pseudo-disk hypergraphs,

    B. Aronov, A. Donakonda, E. Ezra, and R. Pinchasi, “On pseudo-disk hypergraphs,” Computational Geometry, vol. 92, p. 101 687, 2021.doi:https://doi.org/10.1016/ j . comgeo . 2020 . 101687[Online]. Available:https : / / www . sciencedirect . com / science/article/pii/S092577212030081X

    2021

  6. [6]

    Solving Partial Dominating Set and Re- lated Problems Using Twin-Width,

    J. Balab´ an, D. Mock, and P. Rossmanith, “Solving Partial Dominating Set and Re- lated Problems Using Twin-Width,”CoRR, Jun. 2025. arXiv:2504.18218. [Online]. Available:http://arxiv.org/abs/2504.18218

    arXiv 2025

  7. [7]

    Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and vc dimension,

    L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary, and A. Parreau, “Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and vc dimension,”SIAM Journal on Discrete Mathe- matics, vol. 32, no. 2, pp. 902–918, Jan. 2018.doi:10.1137/16m1097833[Online]. Available:http://dx.doi.org/10.1137/16M1097833

    work page doi:10.1137/16m1097833 2018

  8. [8]

    Deciding Twin-Width at Most 4 Is NP-Complete,

    P. Berg´ e,´E. Bonnet, and H. D´ epr´ es, “Deciding Twin-Width at Most 4 Is NP-Complete,” in49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), M. Boja´ nczyk, E. Merelli, and D. P. Woodruff, Eds., ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 229, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum...

    work page doi:10.4230/lipics.icalp 2022

  9. [9]

    Twin- Width VIII: Delineation and Win-Wins,

    ´E. Bonnet, D. Chakraborty, E. J. Kim, N. K¨ ohler, R. Lopes, and S. Thomass´ e, “Twin- Width VIII: Delineation and Win-Wins,” in17th International Symposium on Pa- rameterized and Exact Computation (IPEC 2022), H. Dell and J. Nederlof, Eds., ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 249, Dagstuhl, Germany: Schloss Dagstuhl – Le...

    work page doi:10.4230/lipics.ipec.2022.9 2022

  10. [10]

    Neighbourhood complexity of graphs of bounded twin-width,

    ´E. Bonnet, F. Foucaud, T. Lehtil¨ a, and A. Parreau, “Neighbourhood complexity of graphs of bounded twin-width,”European Journal of Combinatorics, vol. 115, 2024. doi:10.1016/j.ejc.2023.103772

    work page doi:10.1016/j.ejc.2023.103772 2024

  11. [11]

    Twin-width II: small classes,

    ´E. Bonnet, C. Geniet, E. J. Kim, S. Thomass´ e, and R. Watrigant, “Twin-width II: small classes,”Combinatorial Theory, vol. 2, no. 2, 2022.doi:10.5070/C62257876

    work page doi:10.5070/c62257876 2022

  12. [12]

    Twin-width III: Max independent set, min dominating set, and coloring,

    ´E. Bonnet, C. Geniet, E. J. Kim, S. Thomass´ e, and R. Watrigant, “Twin-width III: Max independent set, min dominating set, and coloring,”SIAM Journal on Comput- ing, vol. 53, no. 5, pp. 1602–1640, 2024.doi:10.1137/21M142188X[Online]. Available: https://doi.org/10.1137/21M142188X

    work page doi:10.1137/21m142188x 2024

  13. [13]

    Twin-width VII: groups,

    ´E. Bonnet, C. Geniet, R. Tessera, and S. Thomass´ e, “Twin-width VII: groups,”CoRR, Jul. 2022. arXiv:2204.12330. [Online]. Available:http://arxiv.org/abs/2204. 12330

    arXiv 2022

  14. [14]

    14 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé

    ´E. Bonnet, U. Giocanti, P. O. De Mendez, P. Simon, S. Thomass´ e, and S. Toru´ nczyk, “Twin-Width IV: Ordered Graphs and Matrices,”Journal of the ACM, vol. 71, no. 3, 2024.doi:10.1145/3651151

    work page doi:10.1145/3651151 2024

  15. [15]

    ACM Journal of the ACM (JACM) , year =

    ´E. Bonnet, E. J. Kim, S. Thomass´ e, and R. Watrigant, “Twin-width I: Tractable FO Model Checking,”Journal of the ACM, vol. 69, no. 1, 2022.doi:10.1145/3486655

    work page doi:10.1145/3486655 2022

  16. [16]

    Identifying codes in hereditary classes of graphs and VC-dimension,

    N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, and S. Thomass´ e, “Identifying codes in hereditary classes of graphs and VC-dimension,”SIAM Journal on Discrete Mathe- matics, vol. 29, no. 4, 2015.doi:10.1137/14097879X

    work page doi:10.1137/14097879x 2015

  17. [17]

    Comparing Width Parameters on Graph Classes,

    N. Brettell, A. Munaro, D. Paulusma, and S. Yang, “Comparing Width Parameters on Graph Classes,”CoRR, Apr. 2025. arXiv:2308.05817. [Online]. Available:http: //arxiv.org/abs/2308.05817

    arXiv 2025

  18. [18]

    Cranston and Landon Rabern , title =

    D. W. Cranston and L. Rabern, “Brooks’ Theorem and beyond,”Journal of Graph Theory, vol. 80, no. 3, 2015.doi:10.1002/jgt.21847

    work page doi:10.1002/jgt.21847 2015

  19. [19]

    Twin- width and generalized coloring numbers,

    J. Dreier, J. Gajarsk´ y, Y. Jiang, P. Ossona de Mendez, and J. F. Raymond, “Twin- width and generalized coloring numbers,”Discrete Mathematics, vol. 345, no. 3, 2022. doi:10.1016/j.disc.2021.112746

    work page doi:10.1016/j.disc.2021.112746 2022

  20. [20]

    Identifica- tion, location–domination and metric dimension on interval and permutation graphs. i. bounds,

    F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov, “Identifica- tion, location–domination and metric dimension on interval and permutation graphs. i. bounds,”Theoretical Computer Science, vol. 668, pp. 43–58, 2017.doi:https : / / doi . org / 10 . 1016 / j . tcs . 2017 . 01 . 006[Online]. Available:https : / / www . sciencedirect.com/scie...

    2017

  21. [21]

    Erd˝ os–Hajnal Conjecture for Graphs with Bounded VC-Dimension,

    J. Fox, J. Pach, and A. Suk, “Erd˝ os–Hajnal Conjecture for Graphs with Bounded VC-Dimension,”Discrete and Computational Geometry, vol. 61, no. 4, 2019.doi: 10.1007/s00454-018-0046-5

    work page doi:10.1007/s00454-018-0046-5 2019

  22. [22]

    Cographs: Eigenvalues and Dilworth number,

    E. Ghorbani, “Cographs: Eigenvalues and Dilworth number,”Discrete Mathematics, vol. 342, no. 10, 2019.doi:10.1016/j.disc.2018.09.016

    work page doi:10.1016/j.disc.2018.09.016 2019

  23. [23]

    Interval graphs,

    M. C. Golumbic, “Interval graphs,”Annals of Discrete Mathematics, vol. 57, no. C, pp. 171–202, Jan. 2004.doi:10.1016/S0167-5060(04)80056-6[Online]. Available: https://www.sciencedirect.com/science/article/abs/pii/S0167506004800566 19

    work page doi:10.1016/s0167-5060(04)80056-6 2004

  24. [24]

    Finding small patterns in permutations in linear time , booktitle =

    S. Guillemot and D. Marx, “Finding small patterns in permutations in linear time,” inProceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), C. Chekuri, Ed., Philadelphia, PA: Society for Industrial and Applied Math- ematics, 2014, pp. 82–101.doi:10.1137/1.9781611973402.7[Online]. Available: https://epubs.siam.org/doi/abs/10.1137/...

    work page doi:10.1137/1.9781611973402.7 2014

  25. [25]

    Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension,

    D. Haussler, “Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension,”Journal of Combinatorial Theory, Series A, vol. 69, no. 2, 1995.doi:10.1016/0097-3165(95)90052-7

    work page doi:10.1016/0097-3165(95)90052-7 1995

  26. [26]

    Twin-width of planar graphs is at most 8, and some re- lated bounds,

    P. Hlinˇ en´ y and J. Jedelsk´ y, “Twin-width of planar graphs is at most 8, and some re- lated bounds,”SIAM Journal on Discrete Mathematics, vol. 39, no. 4, pp. 2003–2048, 2025.doi:10.1137/23M1623823eprint:https://doi.org/10.1137/23M1623823. [Online]. Available:https://doi.org/10.1137/23M1623823

    work page doi:10.1137/23m1623823eprint:https://doi.org/10.1137/23m1623823 2003

  27. [27]

    Width parameters beyond tree- width and their applications,

    P. Hlinˇ en´ y, S. I. Oum, D. Seese, and G. Gottlob, “Width parameters beyond tree- width and their applications,”Computer Journal, vol. 51, no. 3, 2008.doi:10.1093/ comjnl/bxm052

    2008

  28. [28]

    Results on learnability and the Vapnik- Chervonenkis dimension,

    N. Linial, Y. Mansour, and R. L. Rivest, “Results on learnability and the Vapnik- Chervonenkis dimension,”Information and Computation, vol. 90, no. 1, 1991.doi: 10.1016/0890-5401(91)90058-A

    work page doi:10.1016/0890-5401(91)90058-a 1991

  29. [29]

    Induced subgraph density. VI. Bounded VC- dimension,

    T. Nguyen, A. Scott, and P. Seymour, “Induced subgraph density. VI. Bounded VC- dimension,”CoRR, Sep. 2025. arXiv:2312 . 15572. [Online]. Available:http : / / arxiv.org/abs/2312.15572

    arXiv 2025

  30. [30]

    On limited nondeterminism and the com- plexity of the V-C dimension,

    C. H. Papadimitriou and M. Yannakakis, “On limited nondeterminism and the com- plexity of the V-C dimension,”Journal of Computer and System Sciences, vol. 53, no. 2, 1996.doi:10.1006/jcss.1996.0058

    work page doi:10.1006/jcss.1996.0058 1996

  31. [31]

    Ordered graphs of bounded twin-width,

    P. Simon and S. Toru´ nczyk, “Ordered graphs of bounded twin-width,”CoRR, Feb

  32. [32]

    [Online]

    arXiv:2102.06881. [Online]. Available:http://arxiv.org/abs/2102.06881

    arXiv

  33. [33]

    Bounded Twin-Width Graphs are Polynomiallyχ- Bounded,

    S. Thomass´ e and R. Bourneuf, “Bounded Twin-Width Graphs are Polynomiallyχ- Bounded,”Advances in Combinatorics, 2025.doi:10.19086/aic.2025.2

    work page doi:10.19086/aic.2025.2 2025

  34. [34]

    Roman Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science

    V. N. Vapnik and A. Y. Chervonenkis, “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities,”Theory of Probability & Its Applications, vol. 16, no. 2, 1971.doi:10.1137/1116025 Appendices A The Twin-width of Split, Bipartite, and Cobipartite Graphs We need two additional definitions in this section. Aconference graphof orderni...

    work page doi:10.1137/1116025 1971