We study graphtheoretic 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
 NSFPAR ID:
 10047495
 Publisher / Repository:
 Oxford University Press (OUP)
 Date Published:
 Journal Name:
 Proceedings of the London Mathematical Society
 Volume:
 116
 Issue:
 4
 ISSN:
 00246115
 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. SVapproximation 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 unitcircle (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 lineartime algorithm for SVsparsifying (and hence UCsparsifying) 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 blackbox reduction from SVsparsifying Eulerian directed graphs to SVsparsifying undirected graphs; such a directedtoundirected reduction was not known for previous notions of spectral approximation.more » « less