Diameter and spectral gap for planar graphs

Abstract

We prove that the spectral gap of a finite planar graph $X$ is bounded by $λ_1(X)\le C(\frac{\log(\diam X)}{\diam X})^2$ where $C$ depends only on the degree of $X$. We then give a sequence of such graphs showing the the above estimate cannot be improved. This yields a negative answer to a question of Benjamini and Curien on the mixing times of the simple random walk on planar graphs.

Fixed an error. Streamlined proof

Cited by in corpus (1)

• A note on mixing times of planar random walks