REVIEW 3 minor 4 references
Row pathwidth of complete binary trees
T0 review · 0 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that any strong-product-plus-path representation of the height-h complete binary tree T_h requires a row graph of pathwidth at least floor((h+1)/16), settling rpw(T_h)=Theta(h).
desk verdict A short, self-contained proof that the row pathwidth of complete binary trees is linear, resolving a 2022 open problem; the AI disclosure is unusual but the math checks out. 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 proof's engine is Lemma 2, a structural lemma about path decompositions: for any connected graph H with pw(H)<=k and any vertex z, there is a set Y containing z such that pw(H-Y)<=k-1 and Y meets the ball of radius d around z in at most 2d+1 vertices. This set Y is obtained by taking two shortest paths from z to the first and last bags of a path decomposition; connectivity forces every bag to meet Y, so deleting Y drops the width by one, while two shortest paths give the ball-bound. The lemma is used to split the embedded tree into a small set S of vertices whose H-coordinate lies in Y and whose weight w(T,S)=sum_{v in S}(3/4)^{depth(v)} is bounded by 388, then to apply induction to each component of T-S, whose H-coordinates lie in H-Y and hence have pathwidth at most k-1. The recurrence w(T)<=388*583^k follows, and comparing with w(T_h)=(3/2)^h gives the constant 16.
What would settle it
One concrete way to test the proof is to search all small connected graphs H with pw(H)<=2 and vertices z: if every set Y containing z with pw(H-Y)<=1 has |Y cap B_H(z,d)| >= 2d+2 for some d, Lemma 2 is false; alternatively, an embedding of T_31 into H boxtimes P with pw(H)=1 would contradict Theorem 1.
Extended reading notes
Core claim
The central claim is Theorem 1: for every nonnegative integer h, floor((h+1)/16) <= rpw(T_h). In other words, no matter how the height-h complete binary tree is embedded as a subgraph of H boxtimes P with P a path, the graph H needs pathwidth at least floor((h+1)/16). Since T_h embeds in T_h boxtimes P with P a single vertex, the matching upper bound rpw(T_h) <= pw(T_h)=ceil(h/2) is immediate, so rpw(T_h)=Theta(h). The lower bound follows from a weighted counting argument: with q=3/4, the total weight of T_h is (3/2)^h because it has 2^h leaves at depth h, while an induction using the ball lemma bounds the weight of any such embedded tree by 388*583^k, yielding h < 15 + 16k.
Load-bearing premise
The proof rests on Lemma 2's ball estimate, that from any vertex z of a pathwidth-k connected graph one can delete a set Y, lowering pathwidth to k-1, whose intersection with every radius-d ball around z has size at most 2d+1.
Editorial extensions
If this is right
- The asymptotic row pathwidth of complete binary trees is now known: rpw(T_h)=Theta(h), improving the previous Omega(h/log h) lower bound.
- Because row pathwidth is monotone under taking subgraphs, every graph class that contains arbitrarily large complete binary trees also has row pathwidth growing at least linearly in h.
- The quantified bound gives a concrete obstruction: any representation of T_h in H boxtimes P must use a row graph H whose pathwidth is at least about one sixteenth of the tree height.
- The proof shows the inherent cost of representing binary trees in product structure is linear, not logarithmic.
Reading between the lines
- The constant 16 is an artifact of choosing q=3/4 and of the crude bounds 388 and 583; re-optimizing the weight parameter and the ball-counting constants could improve the multiplicative constant while preserving the linear lower bound.
- The same weighted-counting induction should generalize to d-ary trees by choosing a weight q strictly between 1/d and 1, giving linear lower bounds for their row pathwidth with dimension-dependent constants.
- Because the argument only uses distances along the two coordinates, it may serve as a template for lower bounds on row width parameters of other self-similar trees and tree-like structures.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves Theorem 1: for every nonnegative integer h, floor((h+1)/16) ≤ rpw(T_h), where T_h is the complete binary tree of height h and rpw is the row pathwidth defined via the strong product with a path. The proof is self-contained. Lemma 2 gives a decomposition lemma for a connected graph H with pw(H) ≤ k: there is a set Y containing a prescribed vertex z such that pw(H−Y) ≤ k−1 and |Y∩B_H(z,d)| ≤ 2d+1 for every d. This is used in Lemma 3, an induction on k that bounds the weighted sum w(T)=∑_{v∈T} q^{depth(v)} for any rooted binary tree embedded in H⊠P by 388·583^k when pw(H) ≤ k, with q=3/4. Comparing this bound with the leaf contribution 2^h q^h = (3/2)^h yields the linear lower bound. I checked the induction in Lemma 3 line by line, including the base case, the bound on |{v∈S: depth(v)=d}|, the component decomposition, and the final constant comparison.
Significance. The result resolves an open problem posed by Bose, Dujmović, Javarsineh, Morin, and Wood and improves the previous Ω(h/log h) bound to the optimal Θ(h). The proof is elementary and transparent: it relies only on standard path-decomposition facts, an explicit weighted potential, and a clean induction with explicit constants. The constant 1/16 is not optimized, as the authors state. The paper is a strong contribution to graph product structure theory and is likely to be a useful reference. I verified the arithmetic in Lemma 3, including the identity ∑_{d≥0}(2d+1)^2 q^d = 388 at q=3/4 and the inequalities 388 < (3/2)^15 and 583 < (3/2)^16.
minor comments (3)
- [Section 1 and proof of Theorem 1] Several displayed subscripts and superscripts are missing in the typeset text: '2h leaves' should be '2^h leaves', '2h·qh' should be '2^h·q^h', and 'Th' should be 'T_h'.
- [Title/running head] The running head on page 1 reads 'ROW P A THWIDTH'; it should read 'ROW PATHWIDTH'.
- [Lemma 2 proof] The argument that every bag meets Y relies on the standard fact that the set of bags meeting a connected subgraph is an interval; this fact is cited as folklore, but spelling it out in one sentence would improve readability for the general reader.
Circularity Check
No significant circularity; the proof is self-contained and derives the lower bound from first principles.
full rationale
The derivation is self-contained. Lemma 2 is proved directly from the definition of path decomposition: for a connected subgraph the set of bag indices meeting it is an interval because consecutive vertex intervals overlap along edges, and deleting the two shortest paths Y leaves a path decomposition of H-Y of width at most k-1. The ball estimate |Y ∩ B_H(z,d)| ≤ 2d+1 follows from the two shortest paths contributing at most d+1 vertices each and sharing z. Lemma 3 then applies Lemma 2 to the projection of the root and bounds the S-layer weight by the explicit power series sum (2d+1)^2(3/4)^d = 388; no parameter is fitted to the desired conclusion. The components of T-S are handled by induction with pathwidth at most k-1, and the weight transfer uses only the binary-tree branching factor 2. Theorem 1 combines the lower bound w(T_h) ≥ 2^h(3/4)^h = (3/2)^h with the numeric inequalities 388 < (3/2)^15 and 583 < (3/2)^16; these constants are chosen after the fact but the lower bound is not inserted as an assumption. References [1]-[4] serve as context and motivation only; no load-bearing step invokes a self-citation or an unverified prior theorem of the authors. No equation reduces to its own input, and no fitted quantity is renamed as a prediction. Therefore the circularity score is 0.
Assumptions & free parameters
free parameters (1)
- q (weight base) =
3/4
assumptions (5)
- standard math Path decomposition bags meeting a connected subgraph form an integer interval.
- standard math Pathwidth is monotone under taking subgraphs and induced subgraphs.
- domain assumption The projection of a connected subgraph of a strong product onto either coordinate is connected.
- domain assumption Along a path of length d in a strong product, each coordinate changes by at most d.
- standard math A complete binary tree of height h has 2^h leaves at depth h.
Cite this review
Pith. "Pith review of Row pathwidth of complete binary trees." pith.science (2026). https://pith.science/paper/IW4DTCBH
@misc{pith2026260809495,
author = {Pith},
title = {Pith review of: Row pathwidth of complete binary trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/IW4DTCBH}},
note = {Machine review of arXiv:2608.09495}
}
abstract
We show that if a complete binary tree of height $h$ is isomorphic to a subgraph of the strong product of a graph $H$ and a path, then $\mathrm{pw}(H)$ is $\Omega(h)$. This solves a problem posed by Bose, Dujmovi\'c, Javarsineh, Morin, and Wood (2022). The proof was found by OpenAI's GPT-5.6 Sol Pro.
Reference graph
Works this paper leans on
-
[1]
P. Bose, V. Dujmović, M. Javarsineh, P. Morin, and D. R. Wood. Separating layered treewidth and row treewidth. Discrete Mathematics & Theoretical Computer Science, 24(1):1–10, 2022. arXiv:2105.01230
work page Pith review arXiv 2022
-
[2]
Planar graphs have bounded queue-number
V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood. Planar graphs have bounded queue-number. Journal of the ACM, 67(4):1–38, 2020. arXiv:1904.04791
work page Pith review arXiv 2020
-
[3]
Notes on Graph Product Structure Theory
Z. Dvořák, T. Huynh, G. Joret, C.-H. Liu, and D. R. Wood. Notes on graph product structure theory. In 2019–20 MATRIX Annals, pages 513–533. Springer, 2021. arXiv:2001.08860
work page Pith review arXiv 2019
-
[4]
N. Robertson and P. Seymour. Graph minors. I. Excluding a forest.Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983
work page 1983
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.