Pith. sign in

REVIEW 5 minor 22 references

Separation profiles of hyperbolic planar and apex-minor-free graphs

T0 review · 0 major / 5 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read Hyperbolic planar and apex-minor-free graphs have at most logarithmic separation profiles.

desk verdict Clean affirmative answer to the BST question on logarithmic separation profiles for hyperbolic planar (and apex-minor-free) graphs, with two independent proofs and usable constants. read the letter →

arxiv 2607.07809 v1 pith:IYJKD6KJ submitted 2026-07-08 math.CO math.MG

Joseph P. MacManus , Bobby Miraftab This is my paper · ORCID
classification math.COmath.MG MSC 05C1005C8320F6751F30
keywords separationprofilehyperbolicgraphsplanarapex-minor-freetree-widthtreeapproximationgrid
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper answers a question of Benjamini, Schramm and Timár by proving that every hyperbolic planar graph has a separation profile that grows at most like a constant times the logarithm of n. The same logarithmic bound holds more generally for every connected graph that is hyperbolic and excludes a fixed apex graph as a minor. Separation profiles measure how hard it is to cut finite subgraphs into pieces of half-size or smaller by removing vertices; they are monotone under regular maps and therefore obstruct coarse embeddings. The authors obtain an explicit linear dependence on the hyperbolicity constant in the planar case, and they deduce a matching logarithmic bound on the tree-width of every finite subgraph of such a graph.

What carries the argument

An efficient hull (Proposition 4.2) that enlarges any finite connected subgraph H of a δ-hyperbolic graph to a uniformly quasi-isometrically embedded subgraph F of size O(n⁶); F is then uniformly hyperbolic, so Gromov’s tree-approximation lemma supplies a tree-decomposition of logarithmic ambient diameter that converts into a logarithmic separator via apex-minor-free tree-width control.

What would settle it

Exhibit a single infinite hyperbolic planar graph (or apex-minor-free graph) that contains finite subgraphs on n vertices whose balanced vertex separators must grow faster than any constant multiple of log n.

Watch

Extended reading notes

Core claim

Every connected δ-hyperbolic graph that excludes a fixed apex graph A as a minor has separation profile at most C(A,δ) log₂(n+1). In the special case of planar graphs the constant may be taken linear in δ: sep_Γ(n) ≤ 60 + 120 δ log₂ n.

Load-bearing premise

The hull construction must keep the enlarged subgraph only polynomially larger than the original finite piece while still quasi-isometrically embedding it into the ambient hyperbolic graph.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves that the separation profile of any connected δ-hyperbolic apex-minor-free graph grows at most logarithmically (Theorem A), answering Question 4.5 of Benjamini–Schramm–Timár. For the special case of planar graphs it supplies the explicit bound sep_Γ(n) ≤ 60 + 120 δ log_{2} n (Theorem B). The first proof constructs an efficient hull F of any finite connected subgraph H with |V(F)| = O_δ(n^{6}) that is quasi-isometrically embedded (hence uniformly hyperbolic), obtains logarithmic tree-length via Gromov tree approximation, converts to logarithmic tree-width by the Coudert–Ducoffe–Nisse theorem for apex-minor-free graphs, and extracts a balanced separator. The second proof works with the grid profile of planar graphs, produces a tree-decomposition whose bags have ambient diameter O(δ log n), and uses geodesic loaded cycles inside large grid minors (via the Jordan curve theorem) to force a matching lower bound on bag diameters, yielding the linear-in-δ constant.

Significance. The result settles a natural open question posed in the foundational paper on separation profiles and extends the known logarithmic bound from the hyperbolic plane itself to all hyperbolic planar graphs and, more broadly, to hyperbolic apex-minor-free graphs. The two independent proofs give complementary strengths: Theorem A covers a larger class of graphs, while Theorem B supplies an explicit linear dependence on the hyperbolicity constant. The efficient-hull construction (Proposition 4.2) and the controlled tree-decomposition of Proposition 3.2 are clean and potentially reusable. The paper also recovers, as a corollary, logarithmic tree-width bounds for subgraphs of such graphs, extending earlier results of Chepoi et al. and Dieng–Gavoille.

minor comments (5)
  1. [Theorem B / §5.3] The constant 60 + 120 δ appearing in Theorem B is obtained by chaining several crude estimates (n/4 for the load, /3 from Berger–Seymour, factor 5 from the grid-to-tree-width conversion). A short remark that the constants are not claimed to be optimal, and that modest improvements are possible by tightening the choice of the interior cycle or the load fraction, would be helpful.
  2. [Proposition 4.2] In the proof of Proposition 4.2 the bound |V(Y)| ≤ n^{3} is written as n + (n choose 2)n; the slightly cleaner estimate |V(Y)| ≤ n^{3}/2 + n is available and would improve the final polynomial degree by a constant factor, though this is purely cosmetic.
  3. [Figure 1] Figure 1 is referenced but the caption is minimal; a one-sentence description of the four sides of the geodesic quadrilateral would make the 8δ-slimness argument easier to follow on a first reading.
  4. [Front matter] The date line reads “8th July 2026”; this is presumably a typographical error for 2025 or 2024 and should be corrected.
  5. [§1] A brief forward reference in the introduction to the open question on the cut-width profile (mentioned at the end of §1) would better motivate why the authors work with vertex separators rather than edge separators throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: logarithmic separation bounds derived from Gromov tree approximation, slim triangles, QI stability, and external treewidth/grid lemmas without self-referential definitions or fits.

full rationale

The derivation chains for Theorems A and B are self-contained mathematical arguments. Theorem A enlarges a finite connected subgraph H to an efficient hull F (Proposition 4.2) of polynomial size that is quasi-isometrically embedded (hence uniformly hyperbolic by the standard Bridson–Haefliger stability lemma), applies Gromov’s tree-approximation lemma to obtain logarithmic tree-length, converts to logarithmic tree-width via the external Coudert–Ducoffe–Nisse theorem for apex-minor-free graphs, and extracts a balanced separator by the elementary weighted-centroid property of trees. Theorem B likewise obtains a tree-decomposition of controlled ambient diameter (Proposition 3.2), then uses Berger–Seymour geodesic loaded cycles constructed inside grid minors (via the Jordan curve theorem) to force a logarithmic upper bound on the grid profile, which is equivalent to the separation profile for planar graphs by the external Dvořák–Norin and Grigoriev/Seymour–Thomas theorems. No quantity appearing in the target bounds is defined in terms of sep_Γ itself, no parameters are fitted to data, and the few author-overlapping citations (e.g., the note relating tree-width and separation profiles) are non-load-bearing background. The constructions close by direct estimates and do not reduce to their inputs by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper works entirely inside standard metric graph theory. The only external inputs are classical theorems (Gromov tree approximation, slim triangles, Lipton–Tarjan / Dvořák–Norin, Coudert–Ducoffe–Nisse tree-width vs tree-length for apex-minor-free classes, Berger–Seymour loaded-cycle lemma, Whitney uniqueness). No free parameters are fitted; the constants C(A,δ) and the explicit 60+120δ are derived, not optimized against data. No new physical or combinatorial entities are postulated.

assumptions (4)
  • standard math Gromov’s tree-approximation lemma: any n-point subset of a δ-hyperbolic graph embeds into an R-tree with additive error 2δ log₂ n (Theorem 3.1).
    Invoked as a black box to build the controlled tree-decomposition of Proposition 3.2; the statement is classical.
  • standard math Geodesic triangles (resp. quadrilaterals) in a δ-hyperbolic graph are 4δ-slim (resp. 8δ-slim) (Lemma 2.1).
    Used to prove that geodesics between points of the first hull stay in an 8δ-neighbourhood, enabling the second enlargement.
  • domain assumption For a fixed apex graph A there is c_A such that tw(Γ) ≤ 3 c_A (tl(Γ)+1) for every connected A-minor-free graph Γ (Coudert–Ducoffe–Nisse).
    Converts the logarithmic tree-length of the hull into logarithmic tree-width; the constant c_A is left existential.
  • domain assumption Dvořák–Norin / Hume: the separation profile and the tree-width profile of any graph are linearly equivalent.
    Used to reduce the planar case to bounding grid minors (Proposition 5.2).
invented entities (1)
  • Efficient hull F of a finite subgraph H
    purpose: Restores uniform hyperbolicity while keeping |V(F)| polynomial in |V(H)|, so that tree approximation still yields only a logarithmic tree-length.
    Constructed ad hoc in Proposition 4.2 by two successive geodesic fillings; the construction is new but purely combinatorial and does not introduce new primitives beyond ordinary geodesics.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Separation profiles of hyperbolic planar and apex-minor-free graphs." pith.science (2026). https://pith.science/paper/IYJKD6KJ

@misc{pith2026260707809,
  author       = {Pith},
  title        = {Pith review of: Separation profiles of hyperbolic planar and apex-minor-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IYJKD6KJ}},
  note         = {Machine review of arXiv:2607.07809}
}
read the original abstract

We show that the separation profile of a hyperbolic planar graph and, more generally, a hyperbolic apex-minor-free graph, grows at most logarithmically, answering a question of Benjamini, Schramm, and Tim\'ar in the affirmative.

Figures

Figures reproduced from arXiv: 2607.07809 by the authors.

Figure 1
Figure 1. Geodesic quadrilateral Using the estimate above for vertices of Y , we get dF pp, rq ď dF pp, yq ` dF py, y1 q ` dF py 1 , rq ď 2 ` 16δ ` 1 ˘ ` ` 16δ ` 1 ˘ dΓpy, y1 q ď 2 ` 16δ ` 1 ˘ ` ` 16δ ` 1 ˘`dΓpp, rq ` 2p16δ ` 1q ˘ “ ` 16δ ` 1 ˘ dΓpp, rq ` 2 ` 16δ ` 1 ˘2 ` 2 ` 16δ ` 1 ˘ . The reverse inequality dΓpp, rq ď dF pp, rq holds because F is a subgraph of Γ. Hence the inclusion ι: F ãÑ Γ is a quasi-isometric embedding… view at source ↗
Figure 2
Figure 2. The GLC constructed within a planar grid minor in Lemma 5.6. The vertices of this grid drawing denote arbi￾trary branch sets. 5.3. Deducing Theorem B. We now have all we need to conclude the proof of Theorem B. Theorem B. Every δ-hyperbolic planar graph Γ satisfies sepΓpnq ď 60 ` 120δ log2 pnq for all n ě 1. Proof. Let Γ be a δ-hyperbolic planar graph. Let us assume without loss of generality that Γ is connected. Fi… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Benjamini, O

    I. Benjamini, O. Schramm, and Á. Timár,On the separation profile of infinite graphs, Groups, Geometry, and Dynamics6(2012), no. 4, 639–658

    work page 2012

  2. [2]

    Berger and P

    E. Berger and P. Seymour,Bounded-diameter tree-decompositions, Combinatorica44 (2024), no. 3, 659–674

    work page 2024

  3. [3]

    Berger, C

    N. Berger, C. Kenyon, E. Mossel, and Y. Peres,Glauber dynamics on trees and hy- perbolic graphs, Probability Theory and Related Fields131(2005), no. 3, 311–340

    work page 2005

  4. [4]

    Bielak and M

    H. Bielak and M. Pańczyk,A self-stabilizing algorithm for finding weighted centroid in trees, Annales UMCS Informatica12(2012), no. 2, 27–37

    work page 2012

  5. [5]

    M. R. Bridson and A. Haefliger,Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften, vol. 319, Springer, 1999

    work page 1999

  6. [6]

    Chepoi, F

    V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès,Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs, Proceedings of the twenty-fourth annual symposium on computational geometry, 2008, pp. 59–68

    work page 2008

  7. [7]

    Chepoi, F

    V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, Y. Vaxès, and Y. Xiang,Additive spanners and distance and routing labeling schemes for hyperbolic graphs, Algorith- mica62(2012), no. 3–4, 713–732

    work page 2012

  8. [8]

    Chuzhoy and Z

    J. Chuzhoy and Z. Tan,Towards tight(er) bounds for the excluded grid theorem, Jour- nal of Combinatorial Theory, Series B146(2021), 219–265

    work page 2021

Show all 22 references
  1. [9]

    Coudert, G

    D. Coudert, G. Ducoffe, and N. Nisse,To approximate treewidth, use treelength!, SIAM Journal on Discrete Mathematics30(2016), no. 3, 1424–1436

    2016

  2. [10]

    Dieng and C

    Y. Dieng and C. Gavoille,On the tree-width of planar graphs, Electronic Notes in Discrete Mathematics34(2009), 593–596

    2009

  3. [11]

    Dvořák and S

    Z. Dvořák and S. Norin,Treewidth of graphs with balanced separations, Journal of Combinatorial Theory, Series B137(2019), 137–144

    2019

  4. [12]

    Ghys and P

    E. Ghys and P. de la Harpe,Sur les groupes hyperboliques d’après Mikhael Gromov, Vol. 83, Springer Science & Business Media, 2013

    2013

  5. [13]

    Gournay and C

    A. Gournay and C. Le Coz,Separation profile, isoperimetry, growth and compression, Annales de l’institut fourier, 2023, pp. 1627–1675

    2023

  6. [14]

    Graph and Algorithms

    A.Grigoriev,Tree-width and large grid minors in planar graphs,DiscreteMathematics & Theoretical Computer Science13(2011), no. Graph and Algorithms

    2011

  7. [15]

    Gromov,Hyperbolic groups, Essays in group theory, 1987, pp

    M. Gromov,Hyperbolic groups, Essays in group theory, 1987, pp. 75–263

    1987

  8. [16]

    Houdrouge, B

    H. Houdrouge, B. Miraftab, and P. Morin,Separation number and treewidth, revisited, arXiv preprint arXiv:2503.17112 (2025)

    2025 arXiv

  9. [17]

    Hume,Separation profiles of free products, arXiv preprint arXiv:2604.24462 (2026)

    D. Hume,Separation profiles of free products, arXiv preprint arXiv:2604.24462 (2026)

    2026 arXiv

  10. [18]

    D. Hume, J. M Mackay, and R. Tessera,Poincaré profiles of groups and spaces, Revista Matemática Iberoamericana36(2020), no. 6, 1835–1886

    2020

  11. [19]

    5, 1063–1133

    ,Poincaré profiles of lie groups and a coarse geometric dichotomy, Geometric and Functional Analysis32(2022), no. 5, 1063–1133

    2022

  12. [20]

    Kisfaludi-Bak, J

    S. Kisfaludi-Bak, J. Masaříková, E. J. van Leeuwen, B. Walczak, and K. Węgrzycki, Separator theorem and algorithms for planar hyperbolic graphs, 40th international symposium on computational geometry (socg 2024), 2024, pp. 67:1–67:17

    2024

  13. [21]

    J Lipton and R

    R. J Lipton and R. E. Tarjan,A separator theorem for planar graphs, SIAM Journal on Applied Mathematics36(1979), no. 2, 177–189

    1979

  14. [22]

    P. D. Seymour and R. Thomas,Call routing and the ratcatcher, Combinatorica14 (1994), no. 2, 217–241. School of Mathematics, University of Bristol, Bristol, BS8 1UG, UK, and the Heilbronn Institute for Mathematical Research, Bristol, UK Email address:joseph.macmanus@bristol.ac....

    1994

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.