Short Random Walks on Graphs
Short Random Walks on Graphs
The short-term behavior of random walks on graphs is studied, in particular, the rate at which a random walk discovers new vertices and edges. A conjecture by Linial that the expected time to find $\mathcal{N}$ distinct vertices is $O(\mathcal{N}^3 )$ is proved. In addition, upper bounds of $O(\mathcal{M}^2 )$ on …