Characterizing Hyperbolicity in Graphs

Faisal Leo Quraishi

REVIEW 3 major objections 4 minor 24 references

Characterizing Hyperbolicity in Graphs

T0 review · 3 major / 4 minor · reviewed 2026-07-31 · deepseek-v4-flash

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

Pith's one-line read This paper defines a normalized 0-to-1 measure of tree-likeness for finite graphs and proves a closed-form formula for it on the hyperbolic plane, yielding the exact Gromov constants ln 2 and (√2−1)/√2.

desk verdict The main Γ_H2 theorem survives the reader's objection; the real weakness is the unsupported s(G) 'characterization' claim. read the letter →

arxiv 2607.24096 v2 pith:4OCI7QCP submitted 2026-07-27 math.MG

Faisal Leo Quraishi This is my paper · ORCID

classification math.MG MSC 53C2351F3005C12

keywords Gromovhyperbolicityhyperbolicplanegraphinvariantnormalizedfour-pointconditiondiameterscalingtree-likenesslatticegraphs

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 addresses a blind spot in Gromov's delta-hyperbolicity: on finite graphs the raw delta grows with diameter, masking geometry. It introduces the function Γ_X(x) — the largest delta among quadruples of diameter x in a space X — and a normalized index s(G) that lies between 0 (trees) and 1 (large lattice graphs). The main theorem gives a closed-form formula for Γ on the hyperbolic plane: Γ_H2(x) = x − arccosh(cosh²(x/2)). This formula yields an alternate proof that the best Gromov constant for H^2 is ln 2, and the first theoretical proof that the diameter-scaled supremum δ/D equals (√2−1)/√2. If correct, the framework turns the qualitative notion of tree-likeness into a graded quantity usable on finite networks.

What carries the argument

The central object is the function Γ_X(x)=sup{δ(□): D(□)=x}, which converts the local defect δ of a quadruple into a function of its diameter. The proof that Γ_H2 has the stated closed form rests on two lemmas: one showing any quadruple can be replaced by an intersecting-pair quadruple without decreasing δ (presented via a relabeling argument), and one bounding the 'middle' sum M of such a quadruple using the distance function γ_θ(r) between two points at equal radius r from an origin, whose convexity is derived from the hyperbolic law of cosines. The extremal quadruple is the symmetric four-point set { (ℓ/2,0), (ℓ/2,π/2), (ℓ/2,π), (ℓ/2,3π/2) } in polar coordinates; its δ equals f(ℓ).

What would settle it

Search a fine grid of points in the Poincaré disk at a fixed small diameter (say x=0.1) and compute the maximum δ over all quadruples; if any quadruple exceeds x−arccosh(cosh²(x/2)), the formula fails. Alternatively, exhibit a quadruple of small diameter for which the largest pair sum is non-crossing under every labeling and for which replacing the interior point by the intersection point decreases δ, contradicting Lemma 3.5's asserted relabeling and hence the proof of Theorem 3.4.

Watch

Extended reading notes

Core claim

The paper's central claim is that the hyperbolicity of the hyperbolic plane is exactly governed by Γ_H2(x)=x−arccosh(cosh²(x/2)), an increasing, concave function. This function is realized by a symmetric quadruple equidistant from a center, and the proof shows no quadruple of diameter x can exceed it. The formula is then used in two ways: it recovers the best Gromov δ-constant of H^2 as ln 2, and it proves the optimal constant for δ/diameter scaling is (√2−1)/√2, a value previously supported only numerically. The paper further defines a normalized graph invariant s(G) in [0,1] from Γ, so that trees score 0 and large lattice graphs approach 1.

Load-bearing premise

The upper-bound half of the formula relies on the claim that any quadruple of points in the hyperbolic plane can be relabeled so that its largest pair sum is a crossing sum (|ac|+|bd|) while one point lies inside the triangle; the paper asserts this relabeling is always possible, but the argument does not guarantee it for quadruples with a small, near-Euclidean spread.

Editorial extensions

If this is right

Finite graphs can now be ranked by a single number s(G) in [0,1], with trees at 0 and large lattice graphs approaching 1, giving a graded notion of tree-likeness rather than a yes/no answer.
The exact constants for H^2 — ln 2 for the Gromov four-point condition and (√2−1)/√2 for the diameter-scaled condition — resolve a value that had been known only numerically for the scaled case.
Because Γ_G(x) ≤ x/2 for every graph G, the invariant s(G) is guaranteed to lie in [0,1].
The formula for Γ_H2 implies that Γ_H2(x)/x is non-increasing, so the diameter-scaled hyperbolicity constant is attained in the small-diameter (near-Euclidean) limit.
The paper proposes that if s(G) < s(G'), G is more hyperbolic than G' — a testable ordering for synthetic graph families.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same Γ-function method could be applied to the Euclidean plane and to spheres to calibrate the s-scale against other model geometries, not just trees and lattices.
A practical implication left implicit: computing s(G) requires summing Γ_G over all distances, which is expensive for large graphs; deriving a fast estimator or a closed form for other graph families would make the invariant usable on real networks.
The value (√2−1)/√2 ≈ 0.2929 suggests a universal bound for δ/D in all CAT(−1) spaces, but the paper only proves it for H^2; testing on other negatively curved spaces would be a natural next step.
The proof's dependence on the relabeling lemma suggests a regime of small-diameter quadruples where the extremal configuration may differ from the symmetric one; verifying the formula for very small diameters by direct computation could confirm or refute the claimed universality.

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.

Desk Editor's Note

read the letter

Colleague — quick take on arXiv:2607.24096. The reader's rejection is based on a misreading of Lemma 3.5. The relabeling step is valid: for any quadruple one can label the points so the largest pairing is |ac|+|bd|, and because d lies inside the triangle, it lies inside each of the triangle's angles, so bd still meets ac. The point d' lies beyond d on the ray from b, so |bd'| = |bd| + |dd'|, not the other way around; the inequalities in the lemma then go through and δ(Q') ≥ δ(Q). I checked the chain in Lemma 3.6 as well; the convexity argument and the angle bound are fine. So Theorem 3.4 and its corollaries — the closed-form Γ_H2, the alternate proof of ln 2, and the first theoretical value (√2−1)/√2 for the diameter-scaled four-point condition — are not refuted by the reader's example.

What's actually new here: the closed-form expression for Γ_H2 is genuinely absent from the cited literature; [16] is numerical, [21] only covers the large-diameter limit. The scaled constant proof is a clean consequence of concavity, which is nice.

The soft spot is exactly what the stress-test flags. Section 4.2 defines s(G) and computes it for trees and lattices, and says the smaller s(G) is, the more hyperbolic G is. That's a proposal, not a characterization. No monotonicity with respect to any established hyperbolicity measure, no quasi-isometry invariance, no theorem that s(G)

Minor: the notation S,M,L is used slightly inconsistently between Definition 1.4 and Proposition 2.2, but the proof still works. Also, the s(G) section might benefit from acknowledging that computing Γ_G is nontrivial for arbitrary graphs.

Bottom line: the Γ_H2 part deserves to be published and looked at; the s(G) section needs major revision or a much weaker claim. I'd send this to review. The paper is clearly written and not circular; the main theorem is a real result.

Referee Report

3 major / 4 minor

Summary. The paper introduces the function Γ_X(x), the supremum of Gromov's δ over all quadruples of diameter x in a metric space X. Its main theorem (Theorem 3.4) gives a closed-form formula for Γ on the hyperbolic plane, Γ_H2(x) = x - arccosh(cosh^2(x/2)), and proves monotonicity and concavity. The paper uses this formula to reprove that the best Gromov hyperbolicity constant for H^2 is ln 2 (Corollary 3.7) and to give a theoretical proof of the diameter-scaled four-point constant sup δ/D = (√2-1)/√2 (Section 3.3). For finite graphs, it defines a normalized invariant s(G) = 4∑_{i∈Dist_G} Γ_G(i) / (D(G)(D(G)+1)), computes s(T)=0 for trees and s(L_n)=2n/(2n+1) for lattice graphs, and proposes that s(G) characterizes the hyperbolicity of a finite graph.

Significance. The hyperbolic-plane part of the paper is a genuine mathematical contribution. Theorem 3.4 provides a closed-form expression for the diameter-rescaled hyperbolicity function, confirms empirical observations, and yields new proofs of two known/numerical constants. I have examined the reader's objection to Lemma 3.5 and do not find it valid: in the same-side case, because d is an interior point of triangle abc, the line bd intersects the opposite side ac for any choice of vertex b, and the labels can be chosen so that the largest pair sum is |ac|+|bd|. The proof of Theorem 3.4 is therefore sound in my reading. However, the graph-theoretic claim that s(G) characterizes hyperbolicity is not established by any theorem; Section 4.2 gives only computations for two model graphs and an analogy with the curvature parameter. This is the main weakness of the manuscript as a whole.

major comments (3)

[Section 4.2, Definition 4.2 (and abstract)] The abstract and introduction state that s(G) 'characterizes the hyperbolicity of any finite graph.' The only mathematical content offered is s(T)=0, s(L_n)=2n/(2n+1), and the non-decreasing behavior of the analogous F(k) in Proposition 4.3. No theorem shows that s(G) is monotone with respect to established hyperbolicity constants, that s(G)<s(G') implies G is more hyperbolic than G', or that s is a quasi-isometry invariant. The text itself says 'We propose' rather than proves. This is a load-bearing gap: without a theorem (or a clearly stated conjecture that does not claim characterization), the central advertised contribution is unsupported. The manuscript should either supply such a theorem or revise the abstract/title to present s(G) as a heuristic measure.
[Definition 4.2 and subsequent paragraph] The claim that s(G) always lies in [0,1] uses Proposition 2.2 and the bound ∑_{i=0}^{D} i = D(D+1)/2, which assumes Dist_G contains all integers 0,1,...,D. Definition 4.2 is stated for arbitrary finite weighted graphs. If edge weights are non-integral, Dist_G has a different step size and the same computation gives a constant larger than 1 (e.g., for a lattice with all edge weights 1/2, the normalization exceeds 1). The normalization must be changed, or Definition 4.2 restricted to unweighted graphs, for the [0,1] statement to be correct.
[Section 4.2, Proposition 4.3] The inference from monotonicity of F(k) in the curvature parameter to the proposed graph measure is purely analogical: F(k) is defined for hyperbolic planes of curvature -1/k^2, and its monotonicity is a statement about a one-parameter family of continuous spaces. It does not imply that s(G) orders graphs by hyperbolicity, since there is no demonstrated connection between Γ_G and Γ_{M^2} beyond the shared definition. This should be labeled as motivation, not as part of a proof of the characterization.

minor comments (4)

[Section 3.1, Lemma 3.5] In the same-side case, after the relabeling it would help to note explicitly that the line bd meets segment ac because d is an interior point; the proof implicitly uses this when defining d'.
[Section 4.1, Proposition 4.1] The notation L_n is used both for the graph and the metric space; clarify that the vertex set is {0,...,n}^2 and the metric is the L1 distance.
[Section 3.3] Before applying L'Hôpital's rule, it should be stated that Γ_H2(0)=0 and that the limit is of the form 0/0. The current text jumps from concavity to the limit.
[Throughout] Several inline math expressions have spacing/rendering glitches (e.g., 'Gromov’sδ', 'DistX'). Figure 1 would be clearer if the curvature parameter ζ in the left panel and the asymptote in the right panel were specified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Γ_H2 derivation is analytic and self-contained; the unsupported s(G) characterization and Lemma 3.5 gap are correctness/justification issues, not circularity.

full rationale

The derivation chain is not circular. Γ_H2(x) is defined (Definition 2.1) as a supremum of δ over quadruples of diameter x; Theorem 3.4 derives the closed form from the hyperbolic law of cosines/sines via Lemmas 3.2 and 3.3, with the lower bound supplied by the explicit family □_ℓ and the upper bound by Lemmas 3.5–3.6. Corollaries 3.7 and 3.8 then compute limits of that derived formula; ln 2 and (√2−1)/√2 are outputs, not fitted inputs, and the external works [14], [16], [21] are not used as premises for the derivation. There is no load-bearing self-citation and no ansatz imported solely by citation. The paper's actual weaknesses are non-circular: the same-side relabeling in Lemma 3.5 ('We may now permute the labels a,b,c so that L(□)=|ac|+|bd|') is a geometric justification gap that affects correctness, not a reduction of the theorem to its own assumption; and Definition 4.2 is proposed ('Thus, we propose s(G) as a characterization of hyperbolicity in a graph') without a theorem relating s to an established hyperbolicity ordering, so the abstract's 'characterizes' claim is unsupported but not circular. Score 0.

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

The central theorem relies on standard hyperbolic geometry and on a false relabeling assumption in Lemma 3.5. No free parameters are fitted. s(G) is a proposed invariant without independent evidence.

assumptions (2)

standard math Hyperbolic law of cosines and sines, plus Theorems 1.1 and 1.2 from Harvey [13] on sides and interior angles in the hyperbolic plane.
Used throughout Section 3 for distance computations and the intersection arguments in Lemmas 3.5 and 3.6.
ad hoc to paper In the same-side case of Lemma 3.5, the labels of a,b,c can be permuted so that the largest pairwise sum is |ac|+|bd| while d remains inside the triangle.
This unproved relabeling step is false in general near-Euclidean configurations; it is load-bearing for the upper bound in Theorem 3.4.

invented entities (1)

s(G) normalized hyperbolicity score
purpose: Quantify the degree of hyperbolicity of a finite graph on the interval [0,1].
A new proposed statistic. The paper gives no independent benchmark or proven equivalence with existing hyperbolicity notions, only an analogy with the area function F(k).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Characterizing Hyperbolicity in Graphs." pith.science (2026). https://pith.science/paper/4OCI7QCP

@misc{pith2026260724096,
  author       = {Pith},
  title        = {Pith review of: Characterizing Hyperbolicity in Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4OCI7QCP}},
  note         = {Machine review of arXiv:2607.24096}
}

read the original abstract

Gromov's delta-hyperbolicity, the classical measure of how tree-like a metric space is, works well on spaces with unbounded diameter but behaves poorly on finite graphs, where it depends primarily on diameter rather than geometry. We introduce a function relating Gromov's delta of a quadruple to its diameter and use it to define a normalized invariant that characterizes the hyperbolicity of any finite graph, taking values between zero (trees) and one (large lattice graphs). We derive a closed-form formula for this function on the hyperbolic plane. Using this formula, we give an alternate proof of the best constant of Gromov's delta-hyperbolicity for the hyperbolic plane. We also give the first theoretical proof of the optimal constant for the scaled Gromov four-point condition under diameter scaling, previously known only from numerical computations.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 9 linked inside Pith

[16]

Scaled Gromov four- point condition for network graph curvature computation

Edmond Jonckheere, Poonsuk Lohsoonthorn, and Fariba Ariaei. “Scaled Gromov four- point condition for network graph curvature computation.” In:Internet Math.7.3 (2011), pp.137–177

2011
[21]

Strong hyperbolicity

Bogdan Nica and Ján ˇ Spakula. “Strong hyperbolicity.” In:Groups Geom. Dyn.10.3 (2016), pp.951–964

2016
[1]

Hyper- bolic Embeddings for Near-Optimal Greedy Routing

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Anton Krohmer. “Hyper- bolic Embeddings for Near-Optimal Greedy Routing.” In:ACM Journal of Experimental Algorithmics25.1.3(Mar.2020), pp.1–18

2020
[2]

Sustaining the Internet with Hyperbolic Mapping

Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. “Sustaining the Internet with Hyperbolic Mapping.” In:Nature Communications1(Sept.2010), p.62

2010
[3]

On Comput- ing the Hyperbolicity of Real-World Graphs

Michele Borassi, David Coudert, Pierluigi Crescenzi, and Andrea Marino. “On Comput- ing the Hyperbolicity of Real-World Graphs.” In: Lecture Notes in Computer Science 9294(2015), pp.215–226

2015
[4]

Bridson and André Haefliger.Metric Spaces of Non-Positive Curvature

Martin R. Bridson and André Haefliger.Metric Spaces of Non-Positive Curvature. Vol.319. Grundlehren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 1999

1999
[5]

Neural Embeddings of Graphs in Hyperbolic Space

Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. “Neural Embeddings of Graphs in Hyperbolic Space.” In: (2017). arXiv:1705.10359[stat.ML]

arXiv 2017
[6]

Average Gromov hyperbolicity and the Parisi ansatz

Sourav Chatterjee and Leila Sloman. “Average Gromov hyperbolicity and the Parisi ansatz.” In: (2020). arXiv:1907.03203[math.PR]

arXiv 2020

Show all 24 references

[7]

On the Hyperbolicity of Small-World and Tree-Like Random Graphs

Wei Chen, Wenjie Fang, Guangda Hu, and Michael W. Mahoney. “On the Hyperbolicity of Small-World and Tree-Like Random Graphs.” In: (2013). arXiv:1201.1717[cs.SI]

2013 arXiv
[8]

What is the dimension of citation space?

James R. Clough and Tim S. Evans. “What is the dimension of citation space?” In: Physica A: Statistical Mechanics and its Applications448(Apr.2016),235–247

2016
[9]

Computing the Gromov hyper- bolicity of a discrete metric space

Hervé Fournier, Anas Ismail, and Antoine Vigneron. “Computing the Gromov hyper- bolicity of a discrete metric space.” In: (2015). arXiv:1210.3323[cs.CG]

2015 arXiv
[10]

Hyperbolic Groups

Mikhail Gromov. “Hyperbolic Groups.” In:Essays in Group Theory. Ed. by S. M. Gersten. Vol.8. Mathematical Sciences Research Institute Publications. New York: Springer,1987, pp.75–263

1987
[11]

Random Hyperbolic Graphs: Degree Sequence and Clustering

Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. “Random Hyperbolic Graphs: Degree Sequence and Clustering.” In: (2012). arXiv:1205.1470[math.CO]

2012 arXiv
[12]

On the tree-likeness of hyperbolic spaces

Matthias Hamann. “On the tree-likeness of hyperbolic spaces.” In: (2011). arXiv: 1105.3925[math.MG]

2011 arXiv
[13]

MAA Textbooks

Matthew Harvey.Geometry illuminated. MAA Textbooks. An illustrated introduction to Euclidean and hyperbolic plane geometry. Mathematical Association of America, Washington, DC,2015, pp. xvi+543

2015
[14]

Hyperbolic geometry of earthquake networks

Karla Henricksen and Ilya Zaliapin. “Hyperbolic geometry of earthquake networks.” In: JSM Proceedings, Statistics and the Environment Section. Alexandria, VA: American Statistical Association,2019

2019
[15]

Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity

Pierre Houedry, Nicolas Courty, Florestan Martin-Baillon, Laetitia Chapel, and Titouan Vayer. “Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity.” In: (2025). arXiv:2505.21073[cs.LG]. 19

2025
[17]

Scaled Gromov hyperbolic graphs

Edmond Jonckheere, Poonsuk Lohsoonthorn, and Francis Bonahon. “Scaled Gromov hyperbolic graphs.” In:Journal of Graph Theory57(Feb.2008), pp.157–180

2008
[18]

A combinatorial higher-rank hyperbolicity condition

Martina Jørgensen and Urs Lang. “A combinatorial higher-rank hyperbolicity condition.” In: (2023). arXiv:2206.08153[math.MG]

2023 arXiv
[19]

Hyperbolic geometry of complex networks

Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. “Hyperbolic geometry of complex networks.” In:Phys. Rev. E (3)82.3(2010), pp.036106,18

2010
[20]

Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs

Onuttom Narayan, Iraj Saniee, and Gabriel H. Tucci. “Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs.” In: (2012). arXiv:1009.5700 [math.PR]

2012 arXiv
[22]

Replaying the Geometric Growth of Complex Networks and Application to the AS Internet

Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri V. Krioukov. “Replaying the Geometric Growth of Complex Networks and Application to the AS Internet.” In: CoRRabs/1205.4384(2012). arXiv:1205.4384

2012 arXiv
[23]

HyperbolicEmbeddingofInternetGraphforDistance Estimation and Overlay Construction

YuvalShavittandTomerTankel.“HyperbolicEmbeddingofInternetGraphforDistance Estimation and Overlay Construction.” In:IEEE/ACM Transactions on Networking 16.1(2008), pp.25–36

2008
[24]

Hyperbolic Geometry of the Olfactory Space

Yuansheng Zhou, Brian H. Smith, and Tatyana O. Sharpee. “Hyperbolic Geometry of the Olfactory Space.” In:Science Advances4.8(Aug.2018), eaaq1458. 20

2018

Pith tools

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

[1] [16]

Scaled Gromov four- point condition for network graph curvature computation

Edmond Jonckheere, Poonsuk Lohsoonthorn, and Fariba Ariaei. “Scaled Gromov four- point condition for network graph curvature computation.” In:Internet Math.7.3 (2011), pp.137–177

2011

[2] [21]

Strong hyperbolicity

Bogdan Nica and Ján ˇ Spakula. “Strong hyperbolicity.” In:Groups Geom. Dyn.10.3 (2016), pp.951–964

2016

[3] [1]

Hyper- bolic Embeddings for Near-Optimal Greedy Routing

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Anton Krohmer. “Hyper- bolic Embeddings for Near-Optimal Greedy Routing.” In:ACM Journal of Experimental Algorithmics25.1.3(Mar.2020), pp.1–18

2020

[4] [2]

Sustaining the Internet with Hyperbolic Mapping

Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. “Sustaining the Internet with Hyperbolic Mapping.” In:Nature Communications1(Sept.2010), p.62

2010

[5] [3]

On Comput- ing the Hyperbolicity of Real-World Graphs

Michele Borassi, David Coudert, Pierluigi Crescenzi, and Andrea Marino. “On Comput- ing the Hyperbolicity of Real-World Graphs.” In: Lecture Notes in Computer Science 9294(2015), pp.215–226

2015

[6] [4]

Bridson and André Haefliger.Metric Spaces of Non-Positive Curvature

Martin R. Bridson and André Haefliger.Metric Spaces of Non-Positive Curvature. Vol.319. Grundlehren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 1999

1999

[7] [5]

Neural Embeddings of Graphs in Hyperbolic Space

Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. “Neural Embeddings of Graphs in Hyperbolic Space.” In: (2017). arXiv:1705.10359[stat.ML]

arXiv 2017

[8] [6]

Average Gromov hyperbolicity and the Parisi ansatz

Sourav Chatterjee and Leila Sloman. “Average Gromov hyperbolicity and the Parisi ansatz.” In: (2020). arXiv:1907.03203[math.PR]

arXiv 2020