Average support of closed walks and second eigenvalue multiplicity of the normalized adjacency matrix

Abstract:   We examine random walks on graphs. Bounds on the typical support (number of distinct visited vertices) of a random walk of given length can be deduced from spectral properties of the graph; however, the typical support of a closed walk (one that is conditioned to end at its starting point) is more opaque. We provide such a bound that is polynomial in the length of the walk by estimating the distribution of the Perron eigenvector, which we do in turn by examining electrical flows on the graph. We then use this result to bound the multiplicity of the second eigenvalue of the normalized adjacency matrix of any graph of polylogarithmic maximum degree.

This is joint work with Peter Rasmussen and Nikhil Srivastava.