We study graph-theoretic properties of the trace of a random walk on a
random graph. We show that for any $\varepsilon>0$ there exists $C>1$ such
that the trace of the simple random walk of length $(1+\varepsilon)n\ln{n}$
on the random graph $G\sim\gnp$ for $p>C\ln{n}/n$ is, with high
probability, Hamiltonian and $\Theta(\ln{n})$-connected. In the special
case $p=1$ (i.e.\ when $G=K_n$), we show a hitting time result according to
which, with high probability, exactly one step after the last vertex has
been visited, the trace becomes Hamiltonian, and one step after the last
vertex has been visited for the $k$'th time, the trace becomes
$2k$-connected.
more »
« less
On the trace of random walks on random graphs: ON THE TRACE OF RANDOM WALKS ON RANDOM GRAPHS
- NSF-PAR ID:
- 10047495
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Proceedings of the London Mathematical Society
- Volume:
- 116
- Issue:
- 4
- ISSN:
- 0024-6115
- Page Range / eLocation ID:
- 847 to 877
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SV-approximation is stronger than previous notions of spectral approximation considered in the literature, including spectral approximation of Laplacians for undirected graphs [ST04], standard approximation for directed graphs [CKP + 17], and unit-circle (UC) approximation for directed graphs [AKM + 20]. Further, SV approximation enjoys several useful properties not possessed by previous notions of approximation, e.g., it is preserved under products of randomwalk matrices and bounded matrices. We provide a nearly linear-time algorithm for SV-sparsifying (and hence UC-sparsifying) Eulerian directed graphs, as well as ℓ-step random walks on such graphs, for any ℓ≤poly(n). Combined with the Eulerian scaling algorithms of [CKK + 18], given an arbitrary (not necessarily Eulerian) directed graph and a set S of vertices, we can approximate the stationary probability mass of the (S,Sc) cut in an ℓ-step random walk to within a multiplicative error of 1/polylog(n) and an additive error of 1/poly(n) in nearly linear time. As a starting point for these results, we provide a simple black-box reduction from SV-sparsifying Eulerian directed graphs to SV-sparsifying undirected graphs; such a directed-to-undirected reduction was not known for previous notions of spectral approximation.more » « less
