REVIEW 1 major objections 6 minor 21 references
Treewidth of Products of Graphs with High Treewidth
T0 review · 1 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read The treewidth of a strong product is at least the product of the factors' treewidths.
desk verdict Sharp, clean solution to an open problem on treewidth of strong products, with a sound main proof and only minor gaps (an unproved lemma for a side theorem and a wording typo). read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the bramble number, a parameter equal to treewidth plus one: a bramble is a family of connected vertex sets that pairwise touch, and its order is the size of the smallest hitting set. The proof lifts a bramble from one factor into the strong product and uses the product's edges to show that lifted families over adjacent factor vertices touch, creating larger brambles. It then applies the standard duality that every bramble is hit by some bag of every tree-decomposition, forcing a projection of the decomposition onto the second factor. For pathwidth, the same projection is run with stoppages—symmetric families of cuts dual to pathwidth—and for strict brambles (pairwise intersect
What would settle it
Compute treewidth of G⊠H for a pair of small graphs where both factors have treewidth at least 2; a value below (tw(G)+1)(tw(H)+1)−1 would refute the main theorem. For the strict result, find a strict bramble and a lenient tree-decomposition such that no bag intersects every bramble member; that would invalidate the auxiliary duality used in Theorem 8.
Extended reading notes
Core claim
The central claim, Theorem 1, is that tw(G⊠H) ≥ (tw(G)+1)(tw(H)+1)−1 for all graphs G and H. The proof takes a maximum bramble in G, lifts every member A to A×{v} for each vertex v of H, and observes that the union of these lifted brambles over an edge of H is still a bramble in the strong product. A minimum-width tree-decomposition of the product is then projected: a vertex v of H is placed in a bag of the projected decomposition exactly when the corresponding bag of the product decomposition hits the lifted bramble at v. Standard bramble/tree-decomposition duality forces the projected bags to form a tree-decomposition of H, and size counting gives the inequality. The paper also proves the
Load-bearing premise
The strong-product lower bound assumes the classical bramble–treewidth duality theorem, while the strict-bramble product inequality additionally assumes an unproved companion duality for lenient tree-decompositions; if these dualities fail, the corresponding product bounds collapse.
Editorial extensions
If this is right
- Solves the open problem of whether tw(G⊠H) ≥ c·tw(G)tw(H) with a positive constant: c=1 works.
- The bound is tight because complete graphs K_m ⊠ K_n have treewidth mn−1.
- The Cartesian bound tw(G□H) ≥ ½(tw(G)+1)(tw(H)+1)−1 is best possible up to the constant ½.
- If G and H are graph classes with positive vertex expansion, then any product G□H, G⊠H, or G◦H contains a subgraph of size linear in the product that is an expander.
- The strict bramble number of a Cartesian product is at least the product of the strict bramble numbers of the factors.
Reading between the lines
- The bramble-projection technique is general enough that it likely yields analogous lower bounds for other parameters that have a hitting-set dual, such as other width parameters defined by decompositions.
- The pairing of strong product with bramble number and Cartesian product with strict bramble number suggests a design principle: sparser products need stricter hitting-set families; this could predict which parameter/product pairings are tractable for other products like lexicographic products.
- For expander products, the proof gives existence of a large expander subgraph but no explicit construction; a computational search could reveal whether the constant can be improved for bounded-degree factors.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the treewidth and pathwidth of strong, Cartesian, and lexicographic products. Its main result (Theorem 1) is the lower bound tw(G ⊠ H) ≥ (tw(G)+1)(tw(H)+1)−1, improving on the previously known bound tw(G ⊠ H) ≥ (tw(G)+1)had(H)−1 of Kozawa–Otachi–Yamazaki and Hickingbotham–Wood, and solving the latter authors' open problem with constant c=1. The bound is optimal by the complete-graph example. The proof is a bramble-lifting argument: from a tree-decomposition of G ⊠ H and a maximum-order bramble in G, the author projects each bag to the set of H-vertices whose corresponding lifted bramble it hits, showing the projected bags form a tree-decomposition of H. The paper also proves the analogous pathwidth bound (Theorem 2) via stoppages, a Cartesian-product treewidth bound (Theorem 3) with best-possible constant 1/2, a strict-bramble product inequality (Theorem 8), a non-tightness result between lexicographic and strong products (Theorem 6), and an application to products of expanders (Theorem 16). The central derivations are internally sound; the main unresolved issue is that two facts used in the proof of Theorem 8 are stated without proof.
Significance. If the proofs are completed, this is a substantial contribution. Theorem 1 is a clean, parameter-free improvement over the previous Hadwiger-number bound; since Hadwiger number can be much smaller than treewidth (e.g., for grids), the improvement is real and not merely cosmetic. The bramble-lifting technique is elegant, and the pathwidth analogue via stoppages is nontrivial and appears correct as written. The application to expanders is a nice consequence. The proof of Theorem 8, however, depends on Fact 21 (and Fact 20), which the manuscript asserts without proof or citation. Fact 21 is not an immediate consequence of the cited duality theorem (Theorem 19) as stated, so this missing argument is a load-bearing gap for the strict-bramble product theorem. The main theorem, Theorem 1, does not rely on this gap.
major comments (1)
- [Section 6, Facts 20–21] Facts 20 and 21 are stated as 'basic facts' with proofs 'similar to Facts 9 and 10', but no proof or precise citation is given. Fact 21 is used essentially at the start of the proof of Theorem 8, where the author invokes it to obtain a node whose lenient bag hits each lifted strict bramble S_v. Fact 20 is used in the same proof to establish the vertex-property of (T, ℓ'). Theorem 19 as quoted only asserts equality between the minimum lenient width and sbn(G); it does not directly imply Fact 21. I have checked that both facts are true: for Fact 21, the sets T_A = {t : ℓ(t)∩A≠∅} are nonempty connected subtrees, and for a strict bramble they pairwise intersect, so by the Helly property for trees they have a common node. But the manuscript must supply this argument (or a reference), because as written Theorem 8 is not fully verified.
minor comments (6)
- [Section 2, proof of Theorem 1] In the edge-property paragraph, after 'If U∩V = ∅' the next sentence reads 'On the other hand, there exists w∈U∩V', which is missing the case condition. It should read 'If U∩V ≠ ∅, choose w∈U∩V'.
- [Section 6, proof of Lemma 13] In the second direction of Lemma 13, the sentence 'Since Y⊆X, it follows that (V(G)\X)∪∂X⊆(V(G)\Y)∪∂Y' is not generally true. The subsequent conclusion G[X]∪G[Z]=G does follow directly from the definition of Z=(V(G)\Y)∪∂Y and Y⊆X, so the proof is repairable, but the displayed implication should be corrected.
- [Section 3, proof of Theorem 2] The stoppages in G and H are denoted by the same symbols as the graphs themselves ('Let G be a stoppage ... and let H be a stoppage ...'), which is confusing in plain text. Use calligraphic letters, e.g., \mathcal{G} and \mathcal{H}.
- [End of Section 6, Question 23 discussion] In the private-communication argument, the sentence 'Then (T,β′) is a tree-decompositionG □H' appears to have a typo: it should be 'a tree-decomposition of G ⊠H'.
- [Section 4, proof of Theorem 16] From tw(S) ≥ c|V(G∗H)| and tw(S) ≤ |V(S)|−1 one obtains |V(S)| ≥ c|V(G∗H)|+1, not c|V(G∗H)|−1. The displayed inequality is true but weaker than what follows; the weaker bound is harmless.
- [Section 6, final paragraph] The sentence in the Question 23 argument should also clarify that the orientation of G is chosen with maximum out-degree degen(G), not just any orientation; this is implicit but could be stated explicitly.
Circularity Check
No circularity found; the main theorem is derived from external standard duality facts and contains no fitted-input or self-citation dependency.
full rationale
The paper's central result, Theorem 1, is derived by taking a minimum-width tree-decomposition of G ⊠ H, layering a maximum-order bramble B of G into brambles B_v = {A × {v} : A ∈ B}, and projecting the decomposition onto H. The proof invokes only standard external facts: Seymour–Thomas bramble/treewidth duality (Theorem 4, cited to [20]) and the well-known Facts 9 and 10 (connectedness of the trace of a connected set, and bramble-hitting by a bag). There is no parameter fitted to the target inequality, no quantity renamed as a prediction, and no load-bearing self-citation. Theorems 2, 3, 6, 7, and 8 similarly rely on external duality results (Bienstock–Robertson–Seymour–Thomas for pathwidth; Lardas–Protopapas–Thilikos–Zoros for strict brambles; Grohe–Marx for expansion), plus internal constructions whose inputs are standard definitions and known theorems. The only internal weakness is Fact 21, which is asserted without proof as 'similar to Facts 9 and 10'; this is an unproved lemma used only in Theorem 8, not a circular step and not a fitted input. No definitional equivalence between the claimed conclusions and their hypotheses appears anywhere in the derivation chain.
Assumptions & free parameters
assumptions (7)
- standard math Theorem 4 (Seymour–Thomas): tw(G)+1 = bn(G) for every graph G.
- standard math Fact 9: for a connected set X, the nodes whose bags intersect X form a connected subtree; Fact 10: every bramble is hit by some bag of any tree-decomposition.
- standard math Theorem 12 (Bienstock–Robertson–Seymour–Thomas pathwidth-blockage duality) and Lemma 13 (blockage–stoppage equivalence).
- standard math sbn(G) ≥ 1/2(tw(G)+1) for every graph G.
- standard math Theorem 19 (Lardas et al.): min lenient tree-decomposition width equals sbn(G).
- standard math Grohe–Marx Theorems 14 and 15 relating treewidth and vertex expansion.
- domain assumption Facts 20 and 21: for lenient tree-decompositions, connected sets induce connected node sets, and every strict bramble is hit by a bag.
Cite this review
Pith. "Pith review of Treewidth of Products of Graphs with High Treewidth." pith.science (2026). https://pith.science/paper/4OLFRXT6
@misc{pith2026260716778,
author = {Pith},
title = {Pith review of: Treewidth of Products of Graphs with High Treewidth},
year = {2026},
howpublished = {\url{https://pith.science/paper/4OLFRXT6}},
note = {Machine review of arXiv:2607.16778}
}
abstract
Treewidth is the standard measure for how ``tree-like'' a graph is. This paper studies how the treewidth of a product graph depends on the treewidth of its factors. Kozawa, Otachi, and Yamazaki [2014] and Hickingbotham and Wood [2025] independently showed that $\text{tw}(G\boxtimes H)\geq (\text{tw}(G)+1)\text{had}(H)-1$ for all graphs $G$ and $H$, where $\text{had}(H)$ is the Hadwiger number of $H$. We improve this bound to $\text{tw}(G\boxtimes H)\geq (\text{tw}(G)+1)(\text{tw}(H)+1)-1$, thereby solving an open problem of Hickingbotham and Wood. We also prove analogous product inequalities for pathwidth, Cartesian products, and strict bramble number, which is a parameter that is tied to treewidth. As an application of our results, we show that products of expanders have large subgraphs that are expanders.
Figures
Reference graph
Works this paper leans on
-
[1]
Treewidth and gonality of glued grid graphs.Discrete Appl
Ivan Aidun, Frances Dean, Ralph Morrison, Teresa Yu, and Julie Yuan. Treewidth and gonality of glued grid graphs.Discrete Appl. Math., 279:1–11, 2020
2020
-
[2]
Two short proofs concerning tree- decompositions
Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree- decompositions. Combin. Probab. Comput., 11(6):541–547, 2002
2002
-
[3]
Quickly excluding a forest
Dan Bienstock, Neil Robertson, Paul Seymour, and Robin Thomas. Quickly excluding a forest. J. Combin. Theory Ser. B , 52(2):274–283, 1991
1991
-
[4]
Bodlaender
Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1):1–45, 1998
1998
-
[5]
Graph minors I: A short proof of the path-width theorem
Reinhard Diestel. Graph minors I: A short proof of the path-width theorem. Combin. Probab. Comput., 4(1):27–30, 1995
1995
-
[6]
Graph theory, volume 173 of Graduate Texts in Mathemat- ics
Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathemat- ics. Springer, 6th edition, 2025
2025
-
[7]
Vida Dujmovi ć, Pat Morin, David R. Wood, and David Worley. Grid minors and products, 2025. arXiv:2402.14181
arXiv 2025
-
[8]
On tree width, bramble size, and expansion
Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. J. Combin. Theory Ser. B , 99(1):218–228, 2009
2009
Show all 21 references
-
[9]
Harvey and David R
Daniel J. Harvey and David R. Wood. Parameters tied to treewidth. J. Graph Theory, 84(4):364–385, 2017
2017
-
[10]
Harvey and David R
Daniel J. Harvey and David R. Wood. The treewidth of line graphs. J. Com- bin. Theory Ser. B, 132:157–179, 2018
2018
-
[11]
Robert Hickingbotham and David R. Wood. Structural properties of graph products. J. Graph Theory, 109(2):107–136, 2025
2025
-
[12]
Lower bounds for treewidth of product graphs
Kyohei Kozawa, Yota Otachi, and Koichi Yamazaki. Lower bounds for treewidth of product graphs. Discrete Appl. Math., 162:251–258, 2014
2014
-
[13]
Thilikos, and Dim- itris Zoros
Emmanouil Lardas, Evangelos Protopapas, Dimitrios M. Thilikos, and Dim- itris Zoros. On strict brambles. Graphs Combin., 39(2):24, 2023
2023
-
[14]
Achievable sets, brambles, and sparse treewidth obstructions
Brian Lucena. Achievable sets, brambles, and sparse treewidth obstructions. Discrete Appl. Math., 155(8):1055–1065, 2007
2007
-
[15]
A simple proof of the tree-width duality theorem, 2013
Frédéric Mazoit. A simple proof of the tree-width duality theorem, 2013. arXiv:1309.2266
2013 arXiv
-
[16]
Bruce A. Reed. Tree width and tangles: a new connectivity measure and some applications. In R. A. Bailey, editor, Surveys in Combinatorics, volume 241 of London Math. Soc. Lecture Note Ser. , pages 87–162. Cambridge Uni- versity Press, 1997
1997
-
[17]
Bruce A. Reed. Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, volume 11, pages 85–107. Springer, 2003
2003
-
[18]
Graph minors
Neil Robertson and Paul Seymour. Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B , 41(1):92–114, 1986
1986
-
[19]
A shorter proof of the path-width theorem, 2023
Paul Seymour. A shorter proof of the path-width theorem, 2023. arXiv:2309.05100
2023 arXiv
-
[20]
Graph searching and a min-max theorem for tree-width
Paul Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B , 58(1):22–33, 1993
1993
-
[21]
David R. Wood. Treewidth of Cartesian products of highly connected graphs. J. Graph Theory, 73(3):318–321, 2013. 13
2013
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.