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={\lambda }_1(G)\le {\lambda }_2(G)\le \cdots \le {\lambda }_n(G)$. Motivated by the Alon-Boppana bound and the Ramanujan phenomenon for regular grap…