On Spielman's Laplacian Eigenratio Conjecture and Related Problems

Jie Ma, Quanyu Tang, Yuchang Wang +1

Let $G$ be an $n$-vertex graph with Laplacian eigenvalues $0=\hat{I}{»}_1(G)\le \hat{I}{»}_2(G)\le \cdots \le \hat{I}{»}_n(G)$. Motivated by the Alon-Boppana bound and the Ramanujan phenomenon for regular g…