Let $G = (V,E)$ be an undirected graph and let $L = I - D^{-1/2} A D^{-1/2}$ be its normalized Laplacian matrix. The Cheeger inequality asserts that: $$\frac{\Phi_G^2}{2} \leq \lambda_2 \leq 2 \Phi_G$$ where $\lambda_2$ is the second smallest eigenvalue of $L$ (the smallest is necessarily $0$) and $\Phi_G$ is the optimal isoperimetric ratio of a set of vertices: $$\Phi_G = \min_{vol(S) \leq vol(G)/2} \frac{|\partial S|}{vol(S)}$$ This inequality can be regarded as a quantitative counterpart of the more elementary observation that $\lambda_2 = 0$ if and only if $G$ is disconnected.
Another elementary observation is that $\lambda_{max} = 2$ if and only if $G$ is bipartite. My question is:
Is there a "Cheeger inequality" for $\lambda_{max}$?
If we define $\Psi_G = \max_S \frac{2 |\partial S|}{vol(G)}$ then one can prove that $$\lambda_{max} \geq 2 \Psi_G$$ by adapting the argument used to prove $\lambda_2 \leq 2 \Phi_G$. This is promising, because $|\partial S|$ is a good measure of how far a graph is from being bipartite; in particular, $\Psi_G = 1$ if and only if $G$ is bipartite. Of course, one expects that finding an upper bound for $\lambda_{max}$ should be the hard part, just as the lower bound for $\lambda_2$ is the hard part of the classical Cheeger inequality.
The typical proof of the classical Cheeger inequality uses a certain variational interpretation of $\lambda_2$ and there is a similar interpretation of $\lambda_{max}$. However, it is not clear (to me) how to adapt the proof of the Cheeger inequality to $\lambda_{max}$. But computer experiments suggest that the strategy of the proof of the classical Cheeger inequality should work for $\lambda_{max}$: a sweep over an eigenvector for $\lambda_{max}$ produces a cut with large $\Psi_G$ just as a sweep over an eigenvector for $\lambda_2$ produces a cut with small $\Phi_G$. So I feel there must be something there, and it would kind of surprise me if nobody has worked this out (though I was not able to find anything in the standard spectral graph theory references).
