The maximum relaxation time of a random walk

Sinan G. Aksoy, Fan Chung, Michael Tait +1

We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on $n$ vertices is $(1+o(1))\frac{54}{n^3}$. This minimum is achieved asymptotically…