ON THE HYPERBOLICITY OF RANDOM GRAPHS

Description

Let G = (V, E) be a connected graph with the usual (graph) distance metric d . Introduced by Gromov, G is δ-hyperbolic if for every four vertices u, v, x, y ∈ V , the two largest values of the three sums d(u, v) + d(x, y), d(u, x) + d(v, y), d(u, y) + d(v, x) differ by at most 2δ. In this paper, we determine precisely the value of this hyperbolicity for most binomial random graphs.

Abstract

International audience

Additional details