SHORT RANDOM-WALKS ON GRAPHS

The short-term behavior of random walks on graphs is studied, in parti cular, the rate at which a random walk discovers new vertices and edge s. A conjecture by Linial, that the expected time to find N distinct v ertices is O(N-3) is proved. In addition, upper bounds of O(M(2)) on t he expected time to traverse M edges and of O(MN) on the expected time to either visit N vertices or traverse M edges (whichever comes first ) are proved.