The maximum relaxation time of a random walk

We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on n vertices is (1+o(1))54n3. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to 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 for the spectral gap of the normalized Laplacian. This eigenvalue lower bound is asymptotically best possible.