pith. sign in

arxiv: 2604.24462 · v1 · submitted 2026-04-27 · 🧮 math.CO

Separation profiles of free products

David Hume This is my paper

Pith reviewed 2026-05-08 02:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords separation profiletreewidth profileasymptotic equivalencetree-graded graphsfree productsCayley graphsgraph profiles
0
0 comments X

The pith

The separation and treewidth profiles of graphs are asymptotically equivalent.

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

The paper establishes that the separation profile and the treewidth profile of a graph are asymptotically equivalent. This means they describe the same large-scale cutting behavior up to constant factors. The result follows from applying a known theorem about graph separators. This equivalence permits explicit computation of the separation profile for Cayley graphs of tree-graded graphs by examining only their constituent pieces. Such graphs include the Cayley graphs of free products of finitely generated groups.

Core claim

We deduce that the separation and treewidth profiles of graphs are asymptotically equivalent. As an application, we calculate the separation profiles of Cayley graphs of tree-graded graphs in terms of their pieces. Examples include Cayley graphs of free products of finitely generated groups.

What carries the argument

The asymptotic equivalence between the separation profile and the treewidth profile, which carries the argument by allowing transfer of results and computations to composite graph structures.

Load-bearing premise

The known theorem about graph separators applies directly to infinite Cayley graphs of tree-graded graphs.

What would settle it

A graph where the separation profile and treewidth profile have asymptotically different growth rates, such as a specific Cayley graph of a free product, would show the equivalence fails.

read the original abstract

We deduce from a theorem of Dvorak--Norin that the separation and treewidth profiles of graphs are asymptotically equivalent, resolving a question of Huang--Hume--Kelly--Lam. As an application, we calculate the separation profiles of Cayley graphs of tree-graded graphs in terms of their pieces. Examples of tree-graded graphs include Cayley graphs of free products of finitely generated groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript deduces from a theorem of Dvorak--Norin that the separation and treewidth profiles of graphs are asymptotically equivalent, resolving a question of Huang--Hume--Kelly--Lam. As an application, it calculates the separation profiles of Cayley graphs of tree-graded graphs in terms of their pieces, with examples including Cayley graphs of free products of finitely generated groups.

Significance. If the deduction is justified, the paper resolves an open question on asymptotic equivalence of these profiles and supplies explicit formulas for separation profiles in the class of tree-graded graphs. The approach of reducing the core claim to an existing theorem is efficient; the value lies in the application to free products and the verification that the equivalence carries over to the infinite setting.

major comments (1)
  1. [Main deduction / application to infinite graphs] The central deduction from the Dvorak--Norin theorem: the manuscript states that the theorem directly yields asymptotic equivalence for the graphs considered, including infinite Cayley graphs of tree-graded graphs. However, treewidth and separation results are typically formulated for finite graphs; an explicit lifting argument (e.g., showing that sequences of finite subgraphs or balls witnessing one profile can be chosen to witness the other, or that the suprema/limits commute with the equivalence) is required to pass the relation to the infinite case. Without such a lemma, the claim for Cayley graphs rests on an unverified approximation property.
minor comments (2)
  1. [Abstract] The abstract and introduction could more explicitly state the form of the separation profile (e.g., the precise asymptotic expression in terms of the pieces) rather than only describing it as 'in terms of their pieces.'
  2. [Introduction] Notation for profiles (separation profile vs. treewidth profile) should be introduced with a brief reminder of the definitions from Huang--Hume--Kelly--Lam to make the deduction self-contained for readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need for an explicit argument when extending the Dvorak--Norin theorem to infinite graphs. We address the major comment below.

read point-by-point responses

  1. Referee: The central deduction from the Dvorak--Norin theorem: the manuscript states that the theorem directly yields asymptotic equivalence for the graphs considered, including infinite Cayley graphs of tree-graded graphs. However, treewidth and separation results are typically formulated for finite graphs; an explicit lifting argument (e.g., showing that sequences of finite subgraphs or balls witnessing one profile can be chosen to witness the other, or that the suprema/limits commute with the equivalence) is required to pass the relation to the infinite case. Without such a lemma, the claim for Cayley graphs rests on an unverified approximation property.

    Authors: We agree that an explicit lifting argument improves clarity, even though the profiles for infinite graphs are defined via limits of the corresponding quantities on finite balls or subgraphs. Because the Dvorak--Norin theorem applies to every finite graph and the finite balls in a Cayley graph of a tree-graded graph inherit the tree-graded structure (with the same piece-wise bounds), the asymptotic equivalence passes to the infinite case. To make this rigorous, we will add a short lemma in Section 2 that shows the suprema and limits commute with the equivalence relation when the underlying finite graphs satisfy the hypotheses of Dvorak--Norin. This addresses the referee's concern without altering the main claims. revision: yes

Circularity Check

0 steps flagged

No circularity; central claim deduced from external Dvorak--Norin theorem

full rationale

The paper states it deduces asymptotic equivalence of separation and treewidth profiles directly from the theorem of Dvorak--Norin (an external result by unrelated authors). The application to Cayley graphs of tree-graded graphs and free products is presented as a consequence of this deduction. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the authors' prior work, or ansatzes smuggled via citation appear in the abstract or described derivation. The resolved question of Huang--Hume--Kelly--Lam is merely the target application, not a premise that reduces the argument to self-reference. The derivation chain is therefore self-contained against the cited external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the theorem of Dvorak--Norin as the key external result from which the equivalence is deduced. No free parameters, new axioms, or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Theorem of Dvorak--Norin on separation and treewidth profiles
    The equivalence is deduced directly from this theorem.

pith-pipeline@v0.9.0 · 5335 in / 1069 out tokens · 42130 ms · 2026-05-08T02:31:40.947830+00:00 · methodology

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

13 extracted references · 13 canonical work pages

  1. [1]

    Bodlaender

    Hans L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Fedor V. Fomin, editor, Graph-Theoretic Concepts in Computer Science , pages 1--14, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

    work page 2006

  2. [2]

    On the separation profile of infinite graphs

    Itai Benjamini, Oded Schramm, and \'A dam Tim \'a r. On the separation profile of infinite graphs. Groups Geom. Dyn. , 6(4):639--658, 2012

    work page 2012

  3. [3]

    Poincar\'e profiles of lamplighter diagonal products

    Corentin Le Coz. Poincar\'e profiles of lamplighter diagonal products. Preprint, arXiv:2007.04709 , 2020

    work page arXiv 2007

  4. [4]

    Tree-graded spaces and asymptotic cones of groups

    Cornelia Dru t u and Mark Sapir. Tree-graded spaces and asymptotic cones of groups. Topology , 44(5):959--1058, 2005. With an appendix by Denis Osin and Mark Sapir

    work page 2005

  5. [5]

    Treewidth of graphs with balanced separations

    Zdenek Dvorak and Sergey Norin. Treewidth of graphs with balanced separations. J. Comb. Th. , Series B. 137, 2014

    work page 2014

  6. [6]

    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

    work page 2023

  7. [7]

    Separation profiles of graphs of fractals

    Valeriia Gladkova and Verna Shum. Separation profiles of graphs of fractals. Journal of Topology and Analysis , 13(04):1111--1123, 2021

    work page 2021

  8. [8]

    Kelly, and Ryan Lam

    Wanying Huang, David Hume, Samuel J. Kelly, and Ryan Lam. A coarse geometric approach to graph layout problems. To appear in the Journal of Graph Theory . Preprint, arXiv:2312.07015 , 2023

    work page arXiv 2023

  9. [9]

    David Hume and John M. Mackay. Connecting conformal dimension and Poincaré profiles. Preprint, arXiv:2511.10469 , 2025

    work page arXiv 2025

  10. [10]

    Mackay, and Romain Tessera

    David Hume, John M. Mackay, and Romain Tessera. Poincar\' e profiles of groups and spaces. Rev. Mat. Iberoam. , 36(6):1835--1886, 2020

    work page 2020

  11. [11]

    Mackay, and Romain Tessera

    David Hume, John M. Mackay, and Romain Tessera. Poincar\'e profiles of L ie groups and a coarse geometric dichotomy. Geom. Funct. Anal. , 32:1063--1133, 2022

    work page 2022

  12. [12]

    Quasi-isometries between groups with infinitely many ends

    Panos Papasoglu and Kevin Whyte. Quasi-isometries between groups with infinitely many ends. Comment. Math. Helv. , 77(1):133--144, 2002

    work page 2002

  13. [13]

    Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms , 7(3):309--332, 1986

    work page 1986