Hitting times in the binomial random graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910450754519040 |
|---|---|
| author | Granet, Bertille Joos, Felix Schrodt, Jonathan |
| author_facet | Granet, Bertille Joos, Felix Schrodt, Jonathan |
| contents | Fix $k\geq 2$, choose $\frac{\log n}{n^{(k-1)/k}}\leq p\leq 1-Ω(\frac{\log^4 n}{n})$, and consider $G\sim G(n,p)$. For any pair of vertices $v,w\in V(G)$, we give a simple and precise formula for the expected number of steps that a random walk on $G$ starting at $w$ needs to first arrive at $v$. The formula only depends on basic structural properties of $G$. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing $p$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10756 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hitting times in the binomial random graph Granet, Bertille Joos, Felix Schrodt, Jonathan Combinatorics Probability Fix $k\geq 2$, choose $\frac{\log n}{n^{(k-1)/k}}\leq p\leq 1-Ω(\frac{\log^4 n}{n})$, and consider $G\sim G(n,p)$. For any pair of vertices $v,w\in V(G)$, we give a simple and precise formula for the expected number of steps that a random walk on $G$ starting at $w$ needs to first arrive at $v$. The formula only depends on basic structural properties of $G$. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing $p$. |
| title | Hitting times in the binomial random graph |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2405.10756 |