pith. sign in

arxiv: 2606.07110 · v1 · pith:SLCEUOLAnew · submitted 2026-06-05 · 💻 cs.DM

Entanglement from Expansion: High Rank-Width in Deterministic Graphs

Tristan Cam , Cyril Gavoille , Yvan Le Borgne , Simon Martiel This is my paper

Pith reviewed 2026-06-27 20:11 UTC · model grok-4.3

classification 💻 cs.DM
keywords rank-widthedge expansionCartesian productshypercubesgraph statescut-rankBoolean function analysisentanglement
0
0 comments X

The pith

Deterministic graph families on n vertices achieve rank-width Θ(n) using edge expansion lower bounds.

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

The paper establishes a general method to lower-bound rank-width of regular graphs from their edge expansion properties. It combines edge-isoperimetric inequalities with the strong chromatic index and Jelínek's cut-rank bound, then strengthens the results for Cartesian products by a logarithmic factor via Boolean function analysis. This produces the first known deterministic families with maximum possible rank-width linear in n, addressing a gap where only up to square-root bounds were previously available for such graphs. The work ties these graph measures directly to entanglement in quantum graph states.

Core claim

By bridging edge-isoperimetric inequalities with the strong chromatic index and Jelínek's approach for lower bounding cut-rank, and extending via a generalization of the Kahn-Kalai-Linial theorem, the authors prove that Cartesian products including hypercubes, Hamming graphs, and grids have rank-width Θ(n). These methods yield deterministic families of graphs on n vertices with provably maximum rank-width Θ(n), filling the prior gap for deterministic families exceeding Θ(√n).

What carries the argument

Method deriving rank-width lower bounds from edge expansion via edge-isoperimetric inequalities, strong chromatic index, and Jelínek's cut-rank bound, strengthened by Boolean function analysis.

If this is right

  • Enables preparation of maximally entangled deterministic graph states in constant depth.
  • Establishes rank-width lower bounds for hypercubes, Hamming graphs, and grids that are strengthened by a logarithmic factor.
  • Provides the first deterministic families with rank-width greater than Θ(√n).
  • Connects edge expansion directly to cut-rank and rank-width measures for regular graphs.

Where Pith is reading between the lines

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

  • The expansion-based technique could apply to additional graph families with known isoperimetric properties beyond Cartesian products.
  • High rank-width in deterministic graphs may simplify constructions for quantum states that previously required random methods.
  • The logarithmic strengthening suggests similar analysis could improve bounds in related width parameters like tree-width or clique-width.

Load-bearing premise

The edge-isoperimetric inequalities combined with the strong chromatic index and Jelínek's cut-rank lower bound apply directly to the Cartesian products without additional restrictions that would invalidate the Θ(n) conclusion.

What would settle it

A direct computation or proof showing that the rank-width of the n-dimensional hypercube is o(n) would refute the linear lower bound.

read the original abstract

Entanglement in quantum graph states is intrinsically linked to rank-width, a graph complexity measure introduced by Oum and Seymour. In this work, we enable the preparation of maximally entangled deterministic graph states in constant depth by developing a general method to derive lower bounds on the rank-width of regular graphs from their edge expansion. By bridging edge-isoperimetric inequalities with the strong chromatic index and Jel\'inek's approach for lower bounding cut-rank, we systematically establish lower bounds for the rank-width of Cartesian products, including hypercubes, Hamming graphs, and grids. Extending this framework via Boolean function analysis, using a generalization of the Kahn-Kalai-Linial's Theorem, we strengthen the bounds for all Cartesian products by a non-trivial logarithmic factor. These methods result in the discovery of deterministic families of graphs on $n$ vertices with a provably maximum rank-width $\Theta(n)$. Our results fill the previous gap in the literature for deterministic graph families of rank-width greater than $\Theta(\sqrt{n})$.

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 / 0 minor

Summary. The paper claims a general method to lower-bound rank-width of regular graphs from edge expansion by combining edge-isoperimetric inequalities, the strong chromatic index, and Jelínek's cut-rank bound; it applies this to Cartesian products (hypercubes, Hamming graphs, grids) and strengthens the bounds via a Boolean-function generalization of the KKL theorem, yielding deterministic n-vertex families with rank-width Θ(n) and closing the gap above Θ(√n).

Significance. If correct, the result would supply the first explicit deterministic constructions achieving the information-theoretic maximum rank-width Θ(n), with direct implications for constant-depth preparation of maximally entangled graph states; the combination of isoperimetric and cut-rank techniques plus the logarithmic strengthening would be a notable technical contribution.

major comments (2)
  1. [Abstract] Abstract: the claimed Θ(n) lower bound on rank-width for hypercubes cannot hold, because every cut in the d-dimensional hypercube Q_d (n=2^d) has cut-rank at most d = O(log n) over GF(2) (the biadjacency matrix rows lie in a d-dimensional vector space), implying rw(Q_d) = O(log n) by definition; the same obstruction applies to Hamming graphs.
  2. [Abstract] Abstract: the claimed Θ(n) lower bound for grids is inconsistent with the standard path-decomposition upper bound rw = Θ(√n); the derivation therefore cannot transfer the cited edge-isoperimetric + strong-chromatic-index + Jelínek combination to these Cartesian-product families without an additional hypothesis that excludes the dimensional obstructions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the inconsistencies between our claimed lower bounds and known upper bounds on rank-width for hypercubes, Hamming graphs, and grids. We acknowledge that the referee's observations are correct and that our manuscript contains errors in the application of the method to these families. We will revise the paper to correct the abstract, remove the incorrect claims for these Cartesian products, add discussion of the necessary hypotheses to avoid dimensional obstructions, and clarify the scope of the families to which the Θ(n) bound applies.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claimed Θ(n) lower bound on rank-width for hypercubes cannot hold, because every cut in the d-dimensional hypercube Q_d (n=2^d) has cut-rank at most d = O(log n) over GF(2) (the biadjacency matrix rows lie in a d-dimensional vector space), implying rw(Q_d) = O(log n) by definition; the same obstruction applies to Hamming graphs.

    Authors: We agree with the referee. The vertices of Q_d may be identified with elements of the vector space GF(2)^d; consequently, for any bipartition the rows of the biadjacency matrix over GF(2) lie in a space of dimension at most d, so the cut-rank is at most d = O(log n) and the rank-width is likewise O(log n). The claimed Θ(n) lower bound for hypercubes (and Hamming graphs) is therefore incorrect. In the revised manuscript we will delete these examples from the abstract and from the sections that apply the method, and we will explicitly note that the algebraic structure of these graphs violates the conditions needed for the lower-bound derivation. revision: yes

  2. Referee: [Abstract] Abstract: the claimed Θ(n) lower bound for grids is inconsistent with the standard path-decomposition upper bound rw = Θ(√n); the derivation therefore cannot transfer the cited edge-isoperimetric + strong-chromatic-index + Jelínek combination to these Cartesian-product families without an additional hypothesis that excludes the dimensional obstructions.

    Authors: We concur. An m-by-m grid has N = m² vertices and rank-width Θ(m) = Θ(√N) by standard path-decomposition arguments; a claimed Θ(N) lower bound is therefore impossible. This demonstrates that the combination of edge-isoperimetric inequalities, strong chromatic index, and Jelínek's cut-rank bound cannot be transferred to these families without an extra hypothesis that rules out low-dimensional obstructions. The revised version will (i) remove grids from the list of examples, (ii) state the additional hypotheses required for the method to yield a linear lower bound, and (iii) restrict the Θ(n) claim to families that satisfy those hypotheses. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation applies external theorems to Cartesian products

full rationale

The paper derives rank-width lower bounds by bridging edge-isoperimetric inequalities, strong chromatic index, Jelínek's cut-rank method, and a generalization of the KKL theorem. These are standard external results, not self-citations or internal fits. No step reduces the target Θ(n) bound to a definition, fitted parameter, or self-referential ansatz by construction. The argument is self-contained against the cited external benchmarks, consistent with the reader's assessment of score 2 (minor at most).

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claim rests on standard combinatorial axioms and known external theorems rather than new free parameters or invented entities.

axioms (3)
  • domain assumption Cartesian products of regular graphs remain regular and inherit edge-expansion properties usable for isoperimetric inequalities.
    Invoked when extending the method to hypercubes, Hamming graphs and grids.
  • standard math Jelínek's cut-rank lower bound from strong chromatic index is valid and composes with edge expansion.
    Forms the bridge from expansion to rank-width.
  • domain assumption The generalized Kahn-Kalai-Linial theorem applies to the Boolean functions arising from the graph cuts.
    Used to obtain the extra logarithmic factor.

pith-pipeline@v0.9.1-grok · 5710 in / 1406 out tokens · 31093 ms · 2026-06-27T20:11:59.649386+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

18 extracted references · 10 canonical work pages · 1 internal anchor

  1. [1]

    Collective coin flipping, robust voting schemes and minima of banzhaf values

    4 Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 408–416. IEEE,

    1985

  2. [2]

    The strong chromatic index of Kt,t-free graphs.arXiv preprint arXiv:2603.15207,

    5 Richard Bi, Peter Bradshaw, Abhishek Dhawan, and Jingwei Xu. The strong chromatic index of Kt,t-free graphs.arXiv preprint arXiv:2603.15207,

    arXiv

  3. [3]

    Sunil Chandran, Telikepalli Kavitha, and C.R

    8 L. Sunil Chandran, Telikepalli Kavitha, and C.R. Subramanian. Isoperimetric inequalities and the width parameters of graphs. In9th Annual International Computing & Combinatorics Conference (COCOON), volume 2697 ofLecture Notes in Computer Science, pages 385–393. Springer, July 2003.doi:10.1007/3-540-45071-8_39. 9 Andrew M Childs, Eddie Schoute, and Cem ...

    work page doi:10.1007/3-540-45071-8_39 2003

  4. [4]

    Hypercontractive measures, talagrand’s inequal- ity, and influences

    10 Dario Cordero-Erausquin and Michel Ledoux. Hypercontractive measures, talagrand’s inequal- ity, and influences. InGeometric Aspects of Functional Analysis: Israel Seminar 2006–2010, pages 169–189. Springer,

    2006

  5. [5]

    Preparing graph states forbidding a vertex-minor.arXiv preprint arXiv:2504.00291,

    11 James Davies and Andrew Jena. Preparing graph states forbidding a vertex-minor.arXiv preprint arXiv:2504.00291,

    arXiv

  6. [6]

    Isoperimetry in product graphs.The Electronic Journal of Combinatorics, 32(3):#P3.12, 2025.doi:10.37236/13585

    13 Sahar Diskin and Wojciech Samotij. Isoperimetry in product graphs.The Electronic Journal of Combinatorics, 32(3):#P3.12, 2025.doi:10.37236/13585. 14 Ronen Eldan and Renan Gross. Concentration on the boolean hypercube via pathwise stochastic analysis.Inventiones mathematicae, 230(3):935–994,

    work page doi:10.37236/13585 2025

  7. [7]

    Flammia and Yi-Kai Liu

    20 Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few pauli measurements. Physical Review Letters, 106(23), June 2011.doi:10.1103/physrevlett.106.230501. 21 Fedor V. Fomin, Sang-il Oum, and Dimitrios M. Thilikos. Rank-width and tree-width of H-minor-free graphs.European Journal of Combinatorics, 31(7):1617–1628, October

    work page doi:10.1103/physrevlett.106.230501 2011

  8. [8]

    22 Soumik Ghosh, Dominik Hangleiter, and Jonas Helsen

    doi:10.1016/j.ejc.2010.05.003. 22 Soumik Ghosh, Dominik Hangleiter, and Jonas Helsen. Random regular graph states are complex at almost any depth.PRX Quantum, 6(4):040344,

    work page doi:10.1016/j.ejc.2010.05.003 2010

  9. [9]

    Random 0/1-polytopes expand rapidly

    URL: https: //arxiv.org/abs/2604.09520,arXiv:2604.09520. 24 Lawrence Hueston Harper. Optimal numberings and isoperimetric problems on graphs.Journal of Combinatorial Theory, 1(3):385–393, 1966.doi:10.1016/S0021-9800(66)80059-5. 25 Matthew B Hastings. An area law for one-dimensional quantum systems.Journal of statistical mechanics: theory and experiment, 2...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/s0021-9800(66)80059-5 1966

  10. [10]

    Hoàng and Nicolas Trotignon

    27 Chính T. Hoàng and Nicolas Trotignon. A class of graphs with large rankwidth.Discrete Mathematics, 347(1):113699, January 2024.doi:10.1016/j.disc.2023.113699. 28 Vít Jelínek. The rank-width of the square grid.Discrete Applied Mathematics, 158(7):841–850, April 2010.doi:10.1016/j.dam.2009.02.007. 29 Richard Jozsa and Noah Linden. On the role of entangle...

    work page doi:10.1016/j.disc.2023.113699 2024

  11. [11]

    The influence of variables on boolean functions

    30 Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 68–80. IEEE Computer Society,

    1988

  12. [12]

    Kanj, Michael Pelsmajer, Marcus Schaefer, and Ge Xia

    31 Iyad A. Kanj, Michael Pelsmajer, Marcus Schaefer, and Ge Xia. On the induced matching problem.Journal of Computer and System Sciences, 77(6):1058–1070, November 2011.doi: 10.1016/j.jcss.2010.09.001. 32 Martin Knor and Ľudovít Niepel. Connectivity of iterated line graphs.Discrete applied mathematics, 125(2-3):255–266,

    work page doi:10.1016/j.jcss.2010.09.001 2011

  13. [13]

    com/science/article/pii/S0166218X13003466,doi:10.1016/j.dam.2013.08.005

    URL:https://www.sciencedirect. com/science/article/pii/S0166218X13003466,doi:10.1016/j.dam.2013.08.005. 34 Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura. Complexity of graph-state preparation by clifford circuits.arXiv preprint arXiv:2402.05874,

    work page doi:10.1016/j.dam.2013.08.005 2013

  14. [14]

    Rank-width of random graphs.Journal of Graph Theory, 70(3):339–347, July 2012.doi:10.1002/jgt.20620

    35 Choongbum Lee, Joonkyung Lee, and Sang-il Oum. Rank-width of random graphs.Journal of Graph Theory, 70(3):339–347, July 2012.doi:10.1002/jgt.20620. 36 Choongbum Lee, Joonkyung Lee, and Sang-il Oum. Rank-width of random graphs.Journal of Graph Theory, 70(3):339–347,

    work page doi:10.1002/jgt.20620 2012

  15. [15]

    Treewidth of the generalized kneser graphs.arXiv preprint arXiv:2011.12725,

    39 Ke Liu, Mengyu Cao, and Mei Lu. Treewidth of the generalized kneser graphs.arXiv preprint arXiv:2011.12725,

    arXiv 2011

  16. [16]

    Matrix product state representations.arXiv preprint quant-ph/0608197,

    49 David Perez-Garcia, Frank Verstraete, Michael M Wolf, and J Ignacio Cirac. Matrix product state representations.arXiv preprint quant-ph/0608197,

    Pith/arXiv arXiv

  17. [17]

    Cuts in cartesian products of graphs.arXiv preprint arXiv:1105.3383,

    50 Sushant Sachdeva and Madhur Tulsiani. Cuts in cartesian products of graphs.arXiv preprint arXiv:1105.3383,

    Pith/arXiv arXiv

  18. [18]

    52 Jean-Pierre Tillich

    doi:10.1137/s0097539795293172. 52 Jean-Pierre Tillich. Edge isoperimetric inequalities for product graphs.Discrete Mathematics, 213(1-3):291–320,

    work page doi:10.1137/s0097539795293172