Note on the trace of random walks on pseudorandom graphs
Preprint
Abstract
We study the graph-theoretic properties of the trace of random walks on pseudorandom graphs. We show that for any $\varepsilon>0$, there exists a constant $C$ such that the cover time of an $(n,d,λ)$-graph $G$ with $d/λ\ge C$ is at most $(1+\varepsilon)n\log n$, meaning the expected number of steps needed to reach all vertices at least once is at most $(1+\varepsilon)n\log n$ regardless of the starting vertex. Furthermore, we prove that with high probability, the trace of a random walk of length $(1+\varepsilon)n\log n$ on $G$ is Hamiltonian, regardless of the starting vertex. These results also hold for random $d$-regular graphs with sufficiently large $d$. These findings answer two questions proposed by Frieze, Krivelevich, Michaeli, and Peled [PLMS, 2018]. Notably, our results imply a bound on a stronger version of the cover time: with high probability, all vertices are covered after $(1+\varepsilon)n\log n$ steps, regardless of the starting vertex. Our proofs rely on the spectral properties of the adjacency matrix and the graph expansion. All results are asymptotically optimal.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Hamilton cycles in pseudorandom graphsAdvances in Mathematics, 2024
- Markov Chains and Mixing Times2017
- Cover time of a random graph with a degree sequence II: Allowing vertices of degree twoRandom Structures & Algorithms, 2014
- Cover time of a random graph with given degree sequenceDiscrete Mathematics, 2012
- Sparse pseudo‐random graphs are HamiltonianJournal of Graph Theory, 2002
- On the Cover Time for Random Walks on Random GraphsCombinatorics, Probability and Computing, 1998
- Multiple cover timeRandom Structures & Algorithms, 1996
- Random walks and the effective resistance of networksJournal of Theoretical Probability, 1991
- Bounds on the cover timeJournal of Theoretical Probability, 1989
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988