Subdivided expanders and counterexamples to the Tree Product Conjecture

Andrea Munaro

Subdivided expanders and counterexamples to the Tree Product Conjecture

T0 review · 0 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Subdivided cubic expanders refute the Tree Product Conjecture for every integer d ≥ 2.

desk verdict A clean, correct disproof of the Tree Product Conjecture for every d ≥ 2, built on a genuinely new subdivision scale for cubic expanders; deserves a serious referee. read the letter →

arxiv 2608.04659 v1 pith:6RA3EMST submitted 2026-08-05 math.CO

Andrea Munaro This is my paper · ORCID

classification math.CO MSC 05C4805C7605C40

keywords expandergraphseparatoredgesubdivisionproductstructuretreeconjecturepolynomialgrowthbalancedstrong

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper targets the Tree Product Conjecture, which predicts that every graph whose balls grow at most like $O(r^d)$ should embed as a subgraph of the strong product of $d$ linear-growth trees and a bounded-size clique. If that conjecture were true, every $n$-vertex graph in such a class would have a 2/3-balanced separation of order only $O(n^{1-1/d})$. The paper constructs, for every real $d>1$, an infinite class of graphs with degree-$d$ polynomial growth whose every 2/3-balanced separation has order at least $c n^{1-1/d}\log n$, a logarithmic factor larger than any tree-product embedding could allow. Combining the two bounds disproves the conjecture for every integer $d\geq 2$, leaving only the linear-growth case $d=1$ open.

What carries the argument

The load-bearing object is the $k_n$-subdivision of a cubic expander, with subdivision length $k_n = \lceil (n/\log^d n)^{1/(d-1)}\rceil$, chosen to sit just where slow growth and large separators can coexist. Two cited ingredients carry the argument. A separator lemma for subdivided expanders guarantees that every 2/3-balanced separation of a graph obtained from a cubic $\alpha$-expander by subdividing each edge at most $m$ times has order at least $|V(G')|/(3(1+3m/2)(6/\alpha+2))$; with $\alpha=3/20$ and $m=k_n-1$, this yields separator order $n/126$ in the original expander coordinates. A growth lemma for the subdivision shows, via the elementary inequality $\min\{n,2^q\}\leq q^d n/\log^d n$, that the same graph has degree-$d$ polynomial growth. On the upper side, a periodic level-slicing argument for strong products (graphs on coordinate tuples, with two tuples adjacent exactly when every coordinate is equal or adjacent in its factor) of $d$ linear-growth trees and a clique gives the bound $4ad(3s)^{1/d}N^{1-1/d}$ on balanced-separator order. The logarithmic gap between these two bounds is the contradiction.

What would settle it

For a fixed $d>1$, take a cubic $3/20$-expander on $n$ vertices, subdivide each edge $k_n = \lceil (n/\log^d n)^{1/(d-1)}\rceil$ times, and look for a 2/3-balanced separation of the resulting $N$-vertex graph with order $O(N^{1-1/d})$. Finding such a separator for arbitrarily large $n$ would refute Theorem 3.6; if instead the minimum order stays $\Omega(N^{1-1/d}\log N)$, the theorem's claim is confirmed.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 3.6: for every real $d>1$ there is an infinite class of graphs with degree-$d$ polynomial growth in which every 2/3-balanced separation has order $\Omega(N^{1-1/d}\log N)$, where $N$ is the number of vertices. The examples are subdivided cubic expanders: each edge of a cubic $3/20$-expander on $n$ original vertices is replaced by a path of length $k_n = \lceil (n/\log^d n)^{1/(d-1)}\rceil$. At this particular length the two competing effects balance out: the graph grows slowly enough to satisfy the degree-$d$ growth bound, while the underlying expander structure keeps every balanced separator large. Because any subgraph of a strong product of $d$ linear-growth trees and a clique admits a 2/3-balanced separation of order at most $4ad(3s)^{1/d}N^{1-1/d}$ (Theorem 2.2), the logarithmic lower bound contradicts the conjecture for every integer $d\geq 2$ (Theorem 4.1).

Load-bearing premise

The lower-bound half relies on a cited lemma asserting that moderately subdivided expanders keep every balanced separator large; if that lemma's constants or its dependence on the subdivision length were weaker, the logarithmic gap the whole argument depends on would disappear.

Editorial extensions

If this is right

The Tree Product Conjecture is false for every integer $d\geq 2$; only the $d=1$ linear-growth case remains possible.
The general upper bound of order $O(n^{1-1/d}\log n)$ for balanced separators in degree-$d$ polynomial growth is tight up to constants, because the new class achieves the same order.
Known separator results that remove the logarithmic factor for polynomial-growth graphs must genuinely require an additional geometric dimension hypothesis; the construction shows the factor cannot be removed from growth alone.
For $d=2$, the construction gives quadratic-growth graphs with unbounded layered treewidth (a width measure for decompositions aligned with a vertex layering), since any class with bounded layered treewidth would have balanced separators of order $O(\sqrt{n})$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The choice of subdivision scale suggests a sharp threshold: the logarithmic factor in the separator bound arises exactly when $k_n$ is on the order of $(n/\log^d n)^{1/(d-1)}$, and it is a natural test whether nearby scales produce intermediate separator behaviour.
Resolving the remaining case $d=1$ likely needs a different mechanism: this construction cannot transfer, because subdivisions preserve treewidth while linear-growth graphs have bounded treewidth.
One could try higher-degree expanders in place of cubic ones to see whether the logarithmic gap can be widened or the constants sharpened, though the present paper already works for every real $d>1$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this paper settles the Tree Product Conjecture for every d ≥ 2, leaving only d = 1 open, and the proof is cleaner than you'd expect for a result of this size. The real novelty is the subdivision scale k_n = ceil((n/log^d n)^{1/(d-1)}). Prior work had the d = 4 case via the Heisenberg group; this gives a uniform construction for all d and, as a bonus, shows the Gournay–Le Coz separator bound is optimal and that quadratic growth does not imply bounded layered treewidth.

What the paper does well: Theorem 2.2 is a tidy periodic-slicing argument—each component after deleting the separator projects into a component of T_i - L_i of size O(p), giving separator size O(n^{1-1/d}). The lower-bound half, Theorem 3.6, is checked algebraically with explicit constants. Lemmas 3.1–3.4 bound balls in subdivisions at the right scale, and Lemma 3.5 correctly converts original vertex count to subdivided vertex count. The n/126 separator lower bound from Dvořák's lemma becomes Ω(n_s^{1-1/d} log n_s), and the contradiction with the product upper bound in Theorem 4.1 is direct.

Soft spots: the whole lower bound leans on two external results—Bollobás's cubic expander existence and Dvořák's separator lemma for subdivided expanders. That is not a flaw; both are standard and clearly cited. But the exact form of Lemma 1.3 matters, and the paper would be slightly stronger if it included a proof or a more precise pointer to [9]. I verified the algebra, and even if the '+1' in the denominator were dropped, the bound would still be Ω(n), so the logarithmic gap is genuine. Minor typos in the front matter do nothing to obscure the math. The AI disclosure is handled responsibly—the author states that they reviewed and take responsibility for the content.

This paper is for people working on graph product structure, separators, and polynomial growth. It deserves a serious referee; I would accept it and send it to a strong referee. I'd also cite it in the next year if writing about product structure or separator lower bounds. The reader's take and the stress-test note both hold up—I don't have a meaningful objection to the central claim.

Referee Report

0 major / 4 minor

Summary. The paper disproves the Tree Product Conjecture of Campbell et al. for every integer d ≥ 2. The main technical contribution is Theorem 3.6, which constructs, for every real d > 1, an infinite family of k_n-subdivisions of cubic expanders such that the family has degree-d polynomial growth and every 2/3-balanced separation has order Ω(m^{1-1/d} log m), where m is the number of vertices. The subdivision length is chosen as k_n = ceil((n/log^d n)^{1/(d-1)}). The proof establishes the growth bound via Lemmas 3.1–3.4 and the separator lower bound via Dvořák's Lemma 1.3, which, with the chosen subdivision length, yields a bound n/126 in terms of the original expander order n; Lemma 3.5 then converts this to the desired order in terms of the subdivided order. Theorem 2.2 shows that any n-vertex subgraph of a strong product of d linear-growth trees and a clique has a 2/3-balanced separation of order O(n^{1-1/d}). Comparing the two bounds yields a logarithmic contradiction and hence Theorem 4.1.

Significance. If correct, this result settles all cases d ≥ 2 of the Tree Product Conjecture, leaving only d = 1 open. The construction is elegant and largely self-contained, with explicit constants and no fitted parameters; the only external inputs are Bollobás's expander existence theorem and Dvořák's separator lemma, both cited precisely and applied correctly. The lower bound matches the general upper bound of Gournay and Le Coz up to the logarithmic factor, showing that their result is optimal among degree-d polynomial growth classes. The paper also draws clean corollaries about Assouad–Nagata dimension and layered treewidth. I checked the chain of inequalities in the main theorems and found no gap.

minor comments (4)

[Lemma 3.2] In Lemma 3.2, the quantity q is not defined in the statement; it should be defined as q = ⌈r/k⌉ + 1, and the proof currently introduces q = ⌊r/k⌋ + 1, which is inconsistent with the later equality ⌈r/k⌉ + 1 = q.
[Lemma 3.2, proof] In the proof of Lemma 3.2, the inequality '3|B_G(z,q)| < 9·2^q' is correct but would be clearer if the Moore bound were stated explicitly; this is a presentation point only.
[Theorem 2.2, proof] In the proof of Theorem 2.2, the expression 'n < 3q2d' should be typeset as n < 3q 2^d to avoid ambiguity.
[Lemma 3.5, proof] In the proof of Lemma 3.5, the constant C1 is written as 'd−1 2d−1 (1/3)^{1−1/d}'; it would be clearer to indicate the multiplication explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is self-contained and relies on external expander and separator lemmas.

full rationale

The derivation chain is not circular. The upper-bound half (Theorem 2.2) is proved directly from Lemma 2.1, which is proved within the paper using only the definition of linear growth and elementary tree properties. The lower-bound half (Theorem 3.6) applies two external results: Bollobás's Lemma 1.2 for the existence of cubic 3/20-expanders and Dvořák's Lemma 1.3 for the separator lower bound on subdivided expanders. Neither of these lemmas assumes Conjecture 1.1 or any conclusion of this paper. The subdivision length k_n = ((n/log^d n))^(1/(d-1)) is a parameter choice that is proven, via Lemmas 3.3 and 3.4, to yield degree-d polynomial growth, and via Lemmas 1.3 and 3.5 to yield the desired separator bound; it is not fitted in a way that renames an input as a prediction. The paper's self-citations [10, 11] appear only in motivational remarks about layered tree-independence number and do not support the proof of Theorem 4.1. No uniqueness theorem from the authors' prior work is invoked, and no equation is defined in terms of the target result. The logarithmic gap between Theorem 2.2 and Theorem 3.6 is genuine and is obtained by combining independent external estimates.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data: the constants C0, C1, c are explicit functions of d, and the subdivision length k_n is chosen deterministically from n and d. The proof imports four standard results from the literature, none of which assume the conjecture. No new entities are postulated.

assumptions (4)

standard math Bollobás's existence theorem: for every sufficiently large even n, there is a cubic 3/20-expander on n vertices.
Invoked as Lemma 1.2 in Theorem 3.6 to supply the base expanders that are then subdivided.
standard math Dvořák's Lemma 1.3: if G' is obtained from a cubic α-expander by subdividing each edge at most m times, then every 2/3-balanced separation of G' has order at least |V(G')| divided by [3(1+3m/2)(6/α+2)].
This is the load-bearing external lower bound behind Theorem 3.6.2; with α=3/20 and m=k_n-1 it yields separator order n/126 for the original expander order n.
standard math Moore bound: a cubic graph has at most 3*2^q - 2 vertices within distance q of any vertex.
Used in Lemma 3.2 to bound the number of replacement paths intersecting a ball.
standard math Standard component-to-separator argument: if every component of H-S has at most n/3 vertices, then H has a 2/3-balanced separation with separator S.
Cited to [6, Lemma 7.20] and used at the end of Theorem 2.2 to convert the periodic slicing set into a balanced separation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Subdivided expanders and counterexamples to the Tree Product Conjecture." pith.science (2026). https://pith.science/paper/6RA3EMST

@misc{pith2026260804659,
  author       = {Pith},
  title        = {Pith review of: Subdivided expanders and counterexamples to the Tree Product Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6RA3EMST}},
  note         = {Machine review of arXiv:2608.04659}
}

abstract

Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood (2023) conjectured that graphs of degree-$d$ polynomial growth can be embedded into the strong product of $d$ trees, each with linear growth, and a constant-size complete graph. Very recently, the case $d = 4$ of the conjecture was disproved by Illingworth, Norin and Steiner (2026). In this paper, we provide counterexamples to the conjecture for every integer $d \geq 2$, thus leaving $d=1$ as the only open case. Our counterexamples are appropriately subdivided cubic expanders. Our main contribution is to construct, for every real number $d>1$, subdivisions of cubic expanders with degree-$d$ polynomial growth and whose balanced separators have size $\Omega(n^{1-1/d}\log n)$, where $n$ denotes the number of vertices.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[9]

Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

Zdeněk Dvořák. Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

work page 2016
[1]

Large-scale geometry of Borel graphs of polynomial growth

Anton Bernshteyn and Jing Yu. Large-scale geometry of Borel graphs of polynomial growth. Advances in Mathematics, 473:110290, 2025

work page 2025
[2]

The isoperimetric number of random regular graphs.European Journal of Combinatorics, 9(3):241–244, 1988

Béla Bollobás. The isoperimetric number of random regular graphs.European Journal of Combinatorics, 9(3):241–244, 1988

work page 1988
[3]

Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces.Journal of the European Mathematical Society, 26(10):3739–3791, 2024

Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, and Alexander Scott. Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces.Journal of the European Mathematical Society, 26(10):3739–3791, 2024

work page 2024
[4]

Prosenjit Bose, Vida Dujmovic, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Sep- arating layered treewidth and row treewidth.Discrete Mathematics&Theoretical Computer Science, 24(1), 2022

work page 2022
[5]

Pascal Gollin, Daniel J

Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, and David R. Wood. Graphs of linear growth have bounded treewidth.The Electronic Journal of Combinatorics, 30(3):#P3.1, 2023

work page 2023
[6]

Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

work page 2015
[7]

Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications.Journal of Combinatorial Theory, Series B, 127:111–147, 2017

work page 2017

Show all 19 references

[8]

Zdeněk Dvořák and David R. Wood. Product structure of graph classes with strongly sublinear separators.Innovations in Graph Theory, 2:191–222, 2025

2025
[10]

Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs

Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs. In Erin W. Chambers and Joachim Gudmundsson, editors,39th International Symposium on Computational Geo...

2023
[11]

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs.CoRR, abs/2402.18352, 2024

Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs.CoRR, abs/2402.18352, 2024. URLhttps://arxiv.org/abs/2402.18352

2024 arXiv
[12]

Separation profile, isoperimetry, growth and compression

Antoine Gournay and Corentin Le Coz. Separation profile, isoperimetry, growth and compression. Annales de l’Institut Fourier, 73(4):1627–1675, 2023

2023
[13]

A continuum of expanders.Fundamenta Mathematicae, 238(2):143–152, 2017

David Hume. A continuum of expanders.Fundamenta Mathematicae, 238(2):143–152, 2017

2017
[14]

Disproof of the tree product conjecture via the Heisenberg group.CoRR, abs/2607.03041, 2026

Freddie Illingworth, Sergey Norin, and Raphael Steiner. Disproof of the tree product conjecture via the Heisenberg group.CoRR, abs/2607.03041, 2026. URLhttps://arxiv.org/pdf/2607. 03041

2026 arXiv
[15]

Robert Krauthgamer and James R. Lee. The intrinsic dimensionality of graphs.Combinatorica, 27(5):551–585, 2007

2007
[16]

Robust algorithms for path and cycle problems in geometric intersection graphs

Malory Marin, Jean-Florent Raymond, and Rémi Watrigant. Robust algorithms for path and cycle problems in geometric intersection graphs. In Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri, editors,42nd International Symposium on Computational Geometry (SoCG 2026), volume 367 of...

2026
[17]

Moore graphs and beyond: A survey of the degree/diameter problem.The Electronic Journal of Combinatorics, 20(2):#DS14v2, 2013

Mirka Miller and Jozef Širáň. Moore graphs and beyond: A survey of the degree/diameter problem.The Electronic Journal of Combinatorics, 20(2):#DS14v2, 2013

2013
[18]

Approximation schemes for wireless networks

Tim Nieberg, Johann Hurink, and Walter Kern. Approximation schemes for wireless networks. ACM Transactions on Algorithms, 4(4):Art. 49, 2008

2008
[19]

Polynomial growth and asymptotic dimension.Israel Journal of Mathematics, 255(2):985–1000, 2023

Panos Papasoglu. Polynomial growth and asymptotic dimension.Israel Journal of Mathematics, 255(2):985–1000, 2023. 11

2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [9]

Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

Zdeněk Dvořák. Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016

work page 2016

[2] [1]

Large-scale geometry of Borel graphs of polynomial growth

Anton Bernshteyn and Jing Yu. Large-scale geometry of Borel graphs of polynomial growth. Advances in Mathematics, 473:110290, 2025

work page 2025

[3] [2]

The isoperimetric number of random regular graphs.European Journal of Combinatorics, 9(3):241–244, 1988

Béla Bollobás. The isoperimetric number of random regular graphs.European Journal of Combinatorics, 9(3):241–244, 1988

work page 1988

[4] [3]

Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces.Journal of the European Mathematical Society, 26(10):3739–3791, 2024

Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, and Alexander Scott. Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces.Journal of the European Mathematical Society, 26(10):3739–3791, 2024

work page 2024

[5] [4]

Prosenjit Bose, Vida Dujmovic, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Sep- arating layered treewidth and row treewidth.Discrete Mathematics&Theoretical Computer Science, 24(1), 2022

work page 2022

[6] [5]

Pascal Gollin, Daniel J

Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, and David R. Wood. Graphs of linear growth have bounded treewidth.The Electronic Journal of Combinatorics, 30(3):#P3.1, 2023

work page 2023

[7] [6]

Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

work page 2015

[8] [7]

Vida Dujmović, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications.Journal of Combinatorial Theory, Series B, 127:111–147, 2017

work page 2017