Pith. sign in

REVIEW 1 major objections 7 minor 18 references

Every graph splits along small separators into coarsely inseparable pieces

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · glm-5.2

2026-07-09 21:18 UTC pith:SQUC4REW

load-bearing objection Clean coarse analogue of block-cutvertex tree-decomposition with a fixable gap in Lemma 3.2 the 1 major comments →

arxiv 2607.07030 v1 pith:SQUC4REW submitted 2026-07-08 math.CO

A coarse block-cutvertex tree-decomposition

Sandra Albrechtsen , Agelos Georgakopoulos This is my paper
classification math.CO MSC 05C1205C4005C6351F30
keywords coarse graph theorytree-decompositionblock-cutvertex treecoarse separatorinseparable setgraph partitionquasi-isometry invariant
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The classical block-cutvertex decomposition breaks a connected graph into 2-connected pieces joined at cutvertices. This paper proves a coarse analogue: for every parameter d, every graph admits a tree-decomposition whose adhesion sets (the separators between pieces) have diameter at most 5d+2, and whose bags are (d, 2d+1)-inseparable, meaning no bounded-diameter separator can split two far-apart vertices of the same bag into different components. The key difficulty is that the naive coarse analogue of a cutvertex fails, because the neighborhood of any single vertex has diameter 2 and already separates. The authors overcome this by requiring separators to separate components of large diameter, and by building a layered graph-partition whose quotient graph H captures the coarse separator structure. The block-cutvertex tree of H, after contracting edges at wide cutvertices, yields the desired decomposition. A strengthened variant (Theorem 1.2) enlarges bags slightly so that each outer-torso is intrinsically coarsely inseparable as a graph, not merely relative to the ambient graph.

Core claim

The central construction is a layered graph-partition of G into boxes indexed by a quotient graph H, built from d-wide annuli around a root vertex and their 2(d+1)-near-components. The block-cutvertex tree of H is then modified by contracting edges at cutvertices whose intersection with a block has large diameter (wide cutvertices), producing a tree whose bags are coarsely inseparable in G and whose adhesion sets have bounded diameter. The structural linchpin is Lemma 3.2: vertices lying in boxes of the same block of H are (d, 2d+1)-inseparable in G, proved by a case analysis showing that any bounded-diameter separator either lies near the vertices or can be routed around using the annular.

What carries the argument

The construction uses d-wide annuli A_n = {v : d(o,v) in [nd, (n+1)d)} around a root o, partitions each annulus-intersection into 2(d+1)-near-components (boxes), and contracts boxes to form the quotient graph H. The block-cutvertex tree of H is then pruned by contracting edges at wide cutvertices (those where the block's intersection with the cutvertex box has diameter exceeding 5d+2). Lemma 3.2 proves inseparability within blocks of H via routing around bounded-diameter separators using annular structure. Theorem 1.2 enlarges bags by 5d+3 and applies Lemma 2.1 to obtain intrinsic inseparability of outer-torsos.

Load-bearing premise

The entire argument rests on Lemma 3.2, which asserts that vertices in boxes belonging to the same block of the quotient graph H are inseparable in G. The proof is a detailed case analysis depending on the specific annular construction and the fact that distinct near-components of the same annulus are far apart. If the routing argument in any sub-case, particularly Case 2b where the separator does not meet the component containing u, fails to produce an avoiding path, the bag

What would settle it

A specific graph G and parameter d where the annular partition of Construction 3.1 produces a quotient graph H whose block-cutvertex tree, after the prescribed contractions, yields a bag that is not (d, 2d+1)-inseparable. The most likely failure point is Case 2b of Lemma 3.2: a configuration where the separator S avoids the component C^{i-1}_u but the argument that the box X' avoids S (because X and X' are far apart) breaks down due to an unexpected interaction between the annular layering and the near-component structure.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • A coarse analogue of the Tutte decomposition (decomposing 2-connected graphs into 3-connected pieces along 2-separators) is posed as Problem 1.3, with the expected generalization being adhesion sets coverable by two bounded-diameter sets and bags coarsely 3-connected.
  • The coarse inseparability of bags implies, via the coarse Menger theorem, that bags contain two well-separated paths between any two large-diameter vertex sets, making them coarsely 2-path-connected.
  • The decomposition is invariant under quasi-isometries up to parameter changes, making it applicable to metric spaces beyond graphs.
  • The construction provides a framework for decomposing arbitrary metric spaces along bounded-diameter separators into coarsely rigid pieces, analogous to how JSJ decompositions work for groups.

Where Pith is reading between the lines

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

  • If the coarse Tutte decomposition (Problem 1.3) is achievable, iterating the two-level decomposition (coarse block-cutvertex then coarse Tutte) would yield a hierarchical coarse decomposition of any graph into pieces of increasing coarse connectivity, analogous to the classical block-tutte hierarchy.
  • The layered partition technique (annuli plus near-components) may generalize to other coarse decomposition problems where a direct quotient loses too much metric information, particularly for coarse analogues of graph minor structure theorems.
  • The non-canonicity of the decomposition (noted by the authors) suggests that a canonical version, if it exists, would require a different construction principle, possibly along the lines of coarse medians or centers.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 7 minor

Summary. The paper proves a coarse analogue of the classical block-cutvertex tree-decomposition. The main result (Theorem 1.1) states that for every $d$, every graph $G$ admits a tree-decomposition whose adhesion sets have diameter at most $5d+2$ and whose bags are $(d, 2d+1)$-inseparable. A variant (Theorem 1.2) strengthens this so that the outer-torsos are intrinsically inseparable and the inherited metric is close to the ambient metric. The construction uses a layered $H$-partition (Construction 3.1) based on $d$-wide annuli, then contracts edges of the block-cutvertex tree of $H$ to form the decomposition tree. The proofs of the tree-decomposition axioms and the two main properties are verified explicitly.

Significance. The result fits into the emerging program of coarse graph theory, which seeks metric-space analogues of structural graph decompositions that are invariant under quasi-isometry. The block-cutvertex tree is one of the most fundamental decompositions in graph theory, and obtaining a coarse version is a natural and worthwhile contribution. The notion of $(d,D)$-inseparability is a reasonable and well-motivated substitute for 2-connectivity. The paper is self-contained, with the main construction and verification laid out in detail. The authors also pose a natural follow-up problem (Problem 1.3) on a coarse Tutte decomposition.

major comments (1)
  1. Lemma 3.2, Case 2a: The argument that the path $P_2$ (a shortest $w'$-to-$o$ path) avoids $S$ contains a step that needs clarification. The authors state that $B_G(X', d+1)$ avoids $S$ (which follows from $X, X'$ being at distance at least $2d+2$ and $S$ having diameter at most $d$ and meeting $X$), and then conclude that 'the first $2d+1$ vertices of $P_2$ avoid $S$.' However, the first $2d+1$ vertices of a shortest path from $w' in X'$ need not all lie in $B_G(X', d+1)$; only the first $d+1$ vertices are guaranteed to be within distance $d+1$ of $X'$. The remaining vertices (positions $d+2$ through $2d+1$) could in principle be farther from $X'$ while still inside the annulus $A_i$. The authors then argue that the remaining vertices of $P_2$ lie in $bigcup_{n le i-2} A_n$ and hence avoid $S$. The gap is in justifying that vertices at positions $d+2$ through $2d+1$ are either still in $
minor comments (7)
  1. Section 1, paragraph 2: 'inseperable' should be 'inseparable' (appears multiple times throughout the manuscript, e.g., also in Theorem 1.2(ii) and the proof of Theorem 1.2).
  2. Section 1, paragraph 5: 'slighlty' should be 'slightly'.
  3. Lemma 2.1: The reference to [1, Lemma 3.3] for the first part is fine, but the 'moreover' part references a map phi whose definition could be slightly clearer; in particular, the choice of v' in N_{O'}(v) for v in V(O' - G') is not unique, and it would help to note that any such choice works.
  4. Lemma 3.2, Case 2a: The sentence 'As X, X' are contained in the same component of G - union_{n le i-1} A_n, they are at distance at least 2d+2 from each other' should perhaps say 'same 2(d+1)-near-component structure' or similar; the distance bound comes from Construction 3.1 (distinct near-components of the same annulus are far apart), not merely from being in the same component of G minus the earlier annuli.
  5. Figure 1: The figures are referenced as 1a and 1b but the captions/labels could be more descriptive of the geometric setup (e.g., indicating the annuli and the positions of S, X, X').
  6. Theorem 1.2(iii): The additive distortion bound of 20d+12 follows from Lemma 2.1 with R = 5d+3 and the adhesion diameter bound of 5d+2 (so floor(r/2) = floor((5d+3)/2) which is at most 5d+3 for d >= 0). This is correct but the arithmetic is not spelled out; a brief sentence would help the reader.
  7. The independent result by Baligacs et al. [6] is mentioned; it would be helpful to briefly state which aspects overlap and which are complementary, for the reader's benefit.

Circularity Check

0 steps flagged

No circularity: the proof is self-contained and parameter-free

full rationale

The paper is a pure mathematics result proving a structural decomposition theorem (Theorem 1.1 and Theorem 1.2). The derivation chain is entirely self-contained within Section 3: Construction 3.1 defines the partition, Lemma 3.2 proves inseparability of boxes within the same block via a detailed case analysis, and Lemma 3.3 extends this to type-(B) bags. No parameters are fitted to data and then presented as predictions. The only self-citation is Lemma 2.1 from [1] (co-authored by the first author), which is a standard technical tool about tree-decompositions and additive distortion — it is not load-bearing for the main theorem's correctness and the paper notes a similar lemma appears in [12] by other authors. The constants (5d+2, 2d+1, etc.) arise from the annulus construction and case analysis, not from circular definitions. The skeptic's concern about Lemma 3.2 Case 2a is a correctness question about whether the distance bounds hold, not a circularity issue — the argument does not define a quantity in terms of the result it claims to derive. No self-definitional, fitted-input, or self-citation-chain circularity is present.

Axiom & Free-Parameter Ledger

1 free parameters · 3 axioms · 3 invented entities

The paper introduces no postulated physical entities or fitted parameters. The single free parameter d is universally quantified. The axioms are standard graph-theoretic results. The invented entities are definitions internal to the mathematical framework, each justified by the theorem they enable.

free parameters (1)
  • d
    The parameter d is a free input to Theorems 1.1 and 1.2, controlling the separator diameter bound and the inseparability parameters. It is not fitted to data; it is a universal quantifier: the theorem holds for every d in N.
axioms (3)
  • standard math Every connected graph admits a block-cutvertex tree-decomposition (classical result, used to construct T' from H in Section 3).
    Invoked in the definition of T: 'Let T' be the block-cutvertex tree of H.' This is a standard theorem in graph theory.
  • standard math Lemma 2.1 (from [1]): expanding bags of a tree-decomposition by radius R yields a tree-decomposition, and if adhesion sets have diameter less than r, the identity has additive distortion at most 4R for R >= floor(r/2).
    Used in the proof of Theorem 1.2 to verify properties (i) and (iii). The lemma is cited from a co-authored paper but is a structural fact about tree-decompositions, not circular with the main result.
  • standard math The coarse Menger Theorem for two paths [4, 13]: used to interpret property (ii) as 'coarsely 2-path-connected'.
    Mentioned in the introduction as a consequence, not used in the proof. No circularity concern.
invented entities (3)
  • (d,D)-inseparability independent evidence
    purpose: Coarse analogue of 2-connectivity: a set U is (d,D)-inseparable if no diameter-d set can separate two vertices of U that are both farther than D from the set.
    This is a definition, not a postulated object. Its adequacy is justified by Theorem 1.1 showing it yields the desired decomposition. It is falsifiable in the sense that if no such decomposition existed, the definition would be vacuous.
  • Outer-torso O_t of a bag V_t independent evidence
    purpose: Graph obtained from G by contracting each component of G - V_t into a vertex; used in Theorem 1.2 to state intrinsic inseparability.
    Standard construction in graph minor theory. Not a new postulated entity but a named construction.
  • Block-class independent evidence
    purpose: Equivalence class of blocks of H under the relation of being 'identified' by a wide cutvertex; used to define the nodes of the decomposition tree T.
    A combinatorial definition internal to the construction. Its correctness is verified by the tree-decomposition axiom checks in Section 3.

pith-pipeline@v1.1.0-glm · 13478 in / 2494 out tokens · 221286 ms · 2026-07-09T21:18:33.140848+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of A coarse block-cutvertex tree-decomposition." pith.science (2026). https://pith.science/paper/SQUC4REW

@misc{pith2026260707030,
  author       = {Pith},
  title        = {Pith review of: A coarse block-cutvertex tree-decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQUC4REW}},
  note         = {Machine review of arXiv:2607.07030}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We obtain a coarse version of the block-cutvertex tree-decomposition of a connected graph.

Figures

Figures reproduced from arXiv: 2607.07030 by Agelos Georgakopoulos, Sandra Albrechtsen.

Figure 1
Figure 1. Figure 1: An illustration of the situation in the proof of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

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 · 18 canonical work pages · 5 internal anchors

  1. [1]

    Albrechtsen, R

    S. Albrechtsen, R. Diestel, A.-K. Elm, E. Fluck, R. W. Jacobs, P. Knappe, and P. Wollan. A structural duality for path-decompositions into parts of small radius. Innovations in Graph Theory, 3:207–246, 2026

    work page 2026

  2. [2]

    Albrechtsen, M

    S. Albrechtsen, M. Distel, and A. Georgakopoulos. ExcludingK 2,t as a fat minor. arXiv:2510.14644. 8

    work page arXiv

  3. [3]

    Albrechtsen, M

    S. Albrechtsen, M. Distel, and A. Georgakopoulos. Small counterexamples to the fat minor conjecture. arXiv:2601.05761

    work page arXiv

  4. [4]

    Albrechtsen, T

    S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan. A Menger- Type Theorem for Two Induced Paths.SIAM J. Discrete Math., 38(2):1438–1450, 2024

    work page 2024

  5. [5]

    Albrechtsen, R

    S. Albrechtsen, R. Jacobs, P. Knappe, and P. Wollan. A characterisation of graphs quasi-isometric toK 4-minor-free graphs.Combinatorica, 45:61, 2025

    work page 2025

  6. [6]

    Balig´ acs, V

    J. Balig´ acs, V. Blaˇ zej, J. Czy˙ zewska, Mi. Pilipczuk, and E. Protopapas. A coarse block-cut tree theorem. preprint, 2026

    work page 2026

  7. [7]

    Coarse Balanced Separators in Fat-Minor-Free Graphs

    E. Bonnet, H. Le, Ma. Pilipczuk, and Mi. Pilipczuk. Coarse Balanced Separators in Fat-Minor-Free Graphs. arXiv:2604.11318

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    Chepoi, F

    V. Chepoi, F. F. Dragan, I. Newman, Y. Rabinovich, and Y. Vax` es. Constant Ap- proximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs.Discrete & Computational Geometry, 47(1):187–214, 2012

    work page 2012

  9. [9]

    Distel, U

    M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne, and P. Micek. A coarse Gallai theorem. arXiv:2601.18439

    work page arXiv

  10. [10]

    A coarse-geometry characterization of cacti

    K. Fujiwara and P. Papasoglu. A coarse-geometry characterization of cacti. arXiv:2305.08512

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    Fujiwara and P

    K. Fujiwara and P. Papasoglu. Asymptotic dimension of planes and planar graphs. Trans. Am. Math. Soc., 374:8887–8901, 2021

    work page 2021

  12. [12]

    Georgakopoulos and C

    A. Georgakopoulos and C. Molinari. Quasi-isometries, contractions, and intersec- tion graphs. In preparation

    work page

  13. [13]

    Georgakopoulos and P

    A. Georgakopoulos and P. Papasoglu. Graph minors and metric spaces.Combina- torica, 45:33, 2025

    work page 2025

  14. [14]

    C.-H. Liu. Coarse menger property of quasi-minor excluded graphs and length spaces. arXiv:2605.10068

    work page internal anchor Pith review Pith/arXiv arXiv

  15. [15]

    MacManus

    J. MacManus. Fat minors in finitely presented groups.Combinatorica, 45:40, 2025

    work page 2025

  16. [16]

    Asymptotic structure. I. Coarse tree-width

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. I. Coarse tree-width. arXiv:2501.09839

    work page internal anchor Pith review Pith/arXiv arXiv

  17. [17]

    Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture. arXiv:2508.14332

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    Tutte.Connectivity in graphs.Mathematical Expositions

    W.T. Tutte.Connectivity in graphs.Mathematical Expositions. 15. Toronto: Uni- versity of Toronto Press; London: Oxford University Press. IX, 145 p., 1966. 9

    work page 1966