Cover and Hitting Times of Hyperbolic Random Graphs

MaRDI QIDQ6404990zbMATH OpenFDO

Authors Marcos Kiwi, Markus Schepers, John Sylvester

Publication date 14 July 2022

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stopping times; optimal stopping problems; gambling theory (60G40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range $(2,3)$. In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is $n(logn{)}^2$, the maximum hitting time is $nlogn$, and the average hitting time is $n$. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.

This page was built for publication: Cover and Hitting Times of Hyperbolic Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404990)