RANDOM REGULAR GRAPHS ARE NOT ASYMPTOTICALLY GROMOV HYPERBOLIC

In this paper we prove that random d­regular graphs with d 3 have traffic congestion of the order O(n log3 (n)) where n is the number of nodes and geodesic d-1 routing is used. We also show that these graphs are not asymptotically ­hyperbolic for any non­negative almost surely as n .