Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs. Issue 1 (17th February 2020)

• Record Type: Journal Article
• Authors: Sylvester, John
• Is Part Of: Journal of graph theory. Volume 96:Issue 1(2021)
• Page Start: 44
• Page End: 84
• Publication Date: 2020-02-17
• Subjects: effective resistance -- hitting time -- kirchoff index -- random graph -- random walk; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22551
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We prove a bound on the effective resistance R ( x, y ) between two vertices x, y of a connected graph which contains a suitably well‐connected subgraph. We apply this bound to the Erdős‐Rényi random graph G ( n, p ) with n p = Ω ( log n ), proving that R ( x, y ) concentrates around 1 / d ( x ) + 1 / d ( y ), that is, the sum of reciprocal degrees. We also prove expectation and concentration results for the random walk hitting times, Kirchoff index, cover cost, and the random target time (Kemeny's constant) on G ( n, p ) in the sparsely connected regime log n + log log log n ≤ n p < n 1 / 10 .