The Library
Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
Tools
Tools
Tools
Sylvester, John (2021) Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs. Journal of Graph Theory, 96 (1). pp. 44-84. doi:10.1002/jgt.22551 ISSN 0364-9024.
|
PDF
WRAP-random-walk-hitting-times-sparsely-random-graphs-Sylvester-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1286Kb) | Preview |
Official URL: http://dx.doi.org/10.1002/jgt.22551
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 .
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Random graphs, Random walks (Mathematics) | ||||||||||||
| Journal or Publication Title: | Journal of Graph Theory | ||||||||||||
| Publisher: | John Wiley & Sons Ltd. | ||||||||||||
| ISSN: | 0364-9024 | ||||||||||||
| Official Date: | January 2021 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 96 | ||||||||||||
| Number: | 1 | ||||||||||||
| Page Range: | pp. 44-84 | ||||||||||||
| DOI: | 10.1002/jgt.22551 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
| Date of first compliant deposit: | 13 March 2020 | ||||||||||||
| Date of first compliant Open Access: | 19 March 2020 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
