2015/03/04 by Verónica Hernández, Hernandez, Veronica, Domingo Pestana +3
Mathematics · #05A20 #05C50 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Limits and Structures in Graph Theory #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.1503.01340
openalex publication_date 2015/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If X is a geodesic metric space and x1,x2,x3 ∈ X, a geodesic triangle T=\x1,x2,x3\ is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is δ-hyperbolic in the Gromov sense if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. δ(X) =inf \ δ≥ 0:0.3cm X 0.2cm is 0.2cm δ-hyperbolic \. To compute the hyperbolicity constant is a very hard problem. Then it is natural to try to bound the hyperbolycity constant in terms of some parameters of the graph. Denote by G(n,m) the set of graphs G with n vertices and m edges, and such that every edge has length 1. In this work we estimate A(n,m):=min\δ(G)| G ∈ G(n,m) \ and B(n,m):=max\δ(G)| G ∈ G(n,m) \. In particular, we obtain good bounds for B(n,m), and we compute the precise value of A(n,m) for all values of n and m. Besides, we apply these results to random graphs.