PNNL

Abstract

We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on n vertices is (1 + o(1)) 54/n^3. This minimum is achieved asymptotically by a double-kite graph. Consequently, this leads a sharp upper bounds for the maximum relaxation time of a random walk, settling a conjecture of Aldous and Fill. We also improve an eigenvalue-diameter inequality by giving a new lower bound on the second eigenvalue of the normalized Laplacian, improving a previous result of the second author by a factor of 4.