Spielman–Teng conjecture on bounded-genus graph eigenvalues

The conjecture asks for a sharp upper bound on the second Laplacian eigenvalue of an $n$-vertex graph embedded on a surface of genus $g$, namely $4\lambda_2(G)\lesssim \Delta g/n\u00024$. Earlier work established weaker genus-dependent and minor-free estimates, but did not clearly prove this sharp form.

Known results

• The 2008 literature records $4\lambda_2(G)=O((g+1)^3\Delta/n)\u00024$ and, for $K_h$-minor-free graphs, $4\lambda_2(G)=O(h^6(\log h)\Delta/n)\u00024$.
• A 2010 preprint gives higher-eigenvalue bounds $4\lambda_k=O(\Delta k g(\log g)^2/n)\u00024$ for genus-$g$ graphs and corresponding minor-free estimates.

August 27, 2026 claimed resolution

The preprint On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs claims to establish the conjectured genus-dependent bound and related bounds for minor-free graphs. The resolution and optimality assertions remain unverified.

Current status (as of August 2026): The sharp bound is claimed by a new preprint, while earlier weaker estimates are established and independent verification of the claimed resolution remains open.