{"id":"e29391b4-501d-41ce-b5ce-dc5b7e4f2b38","arxiv_id":"2608.04659","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every integer d≥2, the paper constructs graphs of degree-d polynomial growth whose balanced separators are too large by a logarithmic factor to fit in the conjectured product structure.","lead":"This paper disproves the Tree Product Conjecture for every dimension d≥2, leaving only the one-dimensional case open. It builds slowly growing graphs that are nevertheless hard to cut in half, using carefully subdivided expander graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the construction is internally consistent, and the external separator lemma on which the lower bound rests is applied correctly and robustly.","rationale":"I read the paper in good faith and checked the internal mathematics rather than the citations. The periodic-slicing proof of Theorem 2.2 is correct: the probability calculation, the component-size bound via Lemma 2.1, and the standard greedy completion to a 2/3-balanced separation all hold. The growth analysis in Section 3 is also correct: Lemma 3.1 handles small radii, Lemma 3.2 with the Moore bound handles large radii, and Lemma 3.3 is a valid convexity argument. The choice k_n = ceil((n/log^d n)^{1/(d-1)}) is what produces the extra log factor: Lemma 3.5 gives n = Θ(n_s^{1-1/d} log n_s). In Theorem 3.6 the application of Lemma 1.3 simplifies to exactly n/126, and Theorem 4.1 then yields the contradiction c log |V(G_j)| ≤ constant. The only non-self-contained ingredients are Dvořák's Lemma 1.3 and Bollobás's expander existence; both are standard and correctly quoted. I therefore do not regard the external dependency as a load-bearing concern, and I partially agree with the reader only in the sense that Lemma 1.3 is the most exposed external step worth an independent check, not that it threatens the verdict. The proposed concrete test provides that check in the exact parameter regime used here.","tokens_in":10784,"tokens_out":44859,"duration_ms":450881,"concrete_test":"Independently re-derive the separator lower bound for the k_n-subdivisions directly from edge expansion: show that any 2/3-balanced vertex separator of G_n induces an edge cut in H_n separating at least n/6 branch vertices, so its order is at least n/120, and compare with Lemma 1.3's n/126. If the direct bound holds up to a universal constant, the logarithmic gap against Theorem 2.2 is genuine.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is sound. The upper-bound half (Theorem 2.2) is a correct periodic-slicing argument: each component after deleting S projects into a component of T_i - L_i of size O(p), yielding |D| ≤ q p^d ≤ n/3 and separator size O(n^{1-1/d}). The lower-bound half (Theorem 3.6) checks algebraically: with m = k_n - 1, Lemma 1.3 gives exactly n/126 because |V(G_n)| = n(1+3m/2) and the denominator contains the same factor; Lemma 3.5 correctly converts n = Θ(n_s^{1-1/d} log n_s). The only external dependency is Dvořák's Lemma 1.3, but it is a standard expander-subdivision separator bound. Moreover, even if the '+1' in its denominator were dropped, the bound would still be Ω(n), and a direct edge-expansion argument for subdivided cubic expanders yields the same Ω(n) order. Thus the logarithmic gap against the product-structure upper bound is genuine and the contradiction in Theorem 4.1 goes through. No significant objection identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10954,"tokens_out":20810,"duration_ms":192140,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Lemma 3.2"},{"comment":"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.","section":"Lemma 3.2, proof"},{"comment":"In the proof of Theorem 2.2, the expression 'n < 3q2d' should be typeset as n < 3q 2^d to avoid ambiguity.","section":"Theorem 2.2, proof"},{"comment":"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.","section":"Lemma 3.5, proof"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is mathematically sound and the central claim is fully supported. The only issues I identified are typographical and local; after the minor corrections are made, particularly the definition of q in Lemma 3.2, the paper should be ready for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nThis 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.","headline":"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.","tokens_in":11524,"tokens_out":1574,"would_cite":true,"duration_ms":18530,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C48","05C76","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subdivided cubic expanders refute the Tree Product Conjecture for every integer d ≥ 2.","keywords":["expander graph","separator","edge subdivision","product structure","tree product conjecture","polynomial growth","balanced separator","strong product"],"falsifier":"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.","tokens_in":10542,"feed_emoji":"🌳","tokens_out":13558,"duration_ms":132365,"temperature":0.7,"pith_summary":"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.","feed_headline":"Subdivided expanders refute Tree Product Conjecture for d ≥ 2","feed_subtitle":"They build degree-d growth graphs that need separators a log factor larger than any tree-product embedding allows.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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$."],"forward_implications":["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})$."],"supporting_citations":[{"why":"states the Tree Product Conjecture whose truth is being tested and supplies the definition of growth used throughout.","marker":"[5]"},{"why":"provides the separator lower-bound lemma for moderately subdivided expanders that yields the n/126 lower bound.","marker":"[9]"},{"why":"guarantees the existence of arbitrarily large cubic 3/20-expanders used as the base graphs.","marker":"[2]"},{"why":"supplies the product-of-paths balanced-separator argument that Theorem 2.2 adapts to linear-growth trees.","marker":"[8]"},{"why":"gives the earlier d=4 counterexample and sets the prior state of the conjecture addressed here.","marker":"[14]"},{"why":"gives the O(n^{1-1/d} log n) separator upper bound for degree-d growth that the construction shows is optimal.","marker":"[12]"},{"why":"states the O(n^{1-1/d}) separator result under a geometric dimension bound, whose dimension hypothesis the construction shows cannot be dropped.","marker":"[13]"}],"fun_headline_variants":["Subdivided expanders disprove Tree Product Conjecture for d≥2","Tree Product Conjecture refuted for every d≥2","Expander subdivisions refute Tree Product for d≥2","Counterexamples from expander subdivisions for d≥2","Log separators refute Tree Product Conjecture for d≥2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Subdivided expanders disprove Tree Product Conjecture for d≥2","Tree Product Conjecture refuted for every d≥2","Expander subdivisions refute Tree Product for d≥2","Counterexamples from expander subdivisions for d≥2","Log separators refute Tree Product Conjecture for d≥2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000635,"raw_usage":{"total_tokens":2927,"prompt_tokens":944,"completion_tokens":1983,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":1895}},"tokens_in":560,"tokens_out":1983,"duration_ms":18762,"temperature":1.0,"reasoning_tokens":1895,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:35:37.999494+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Pascal Gollin, Daniel J","cited_arxiv_id":null,"evidence_quote":"states the Tree Product Conjecture whose truth is being tested and supplies the definition of growth used throughout."},{"cited_title":"Sublinear separators, fragility and subexponential expansion.European Journal of Combinatorics, 52:103–119, 2016","cited_arxiv_id":null,"evidence_quote":"provides the separator lower-bound lemma for moderately subdivided expanders that yields the n/126 lower bound."},{"cited_title":"The isoperimetric number of random regular graphs.European Journal of Combinatorics, 9(3):241–244, 1988","cited_arxiv_id":null,"evidence_quote":"guarantees the existence of arbitrarily large cubic 3/20-expanders used as the base graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the product-of-paths balanced-separator argument that Theorem 2.2 adapts to linear-growth trees."},{"cited_title":"Disproof of the tree product conjecture via the Heisenberg group","cited_arxiv_id":"2607.03041","evidence_quote":"gives the earlier d=4 counterexample and sets the prior state of the conjecture addressed here."},{"cited_title":"Separation profile, isoperimetry, growth and compression","cited_arxiv_id":null,"evidence_quote":"gives the O(n^{1-1/d} log n) separator upper bound for degree-d growth that the construction shows is optimal."},{"cited_title":"A continuum of expanders.Fundamenta Mathematicae, 238(2):143–152, 2017","cited_arxiv_id":null,"evidence_quote":"states the O(n^{1-1/d}) separator result under a geometric dimension bound, whose dimension hypothesis the construction shows cannot be dropped."}],"review_version":1}