3
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

You should see information on the Dual Cheeger constant. See for example:

Bauer-Hua-Jost, The dual Cheeger constant and spectra of infinite graphs

http://arxiv.org/abs/1207.3410

and

Liu, Multi-way dual Cheeger constants and spectral bounds of graphs

http://arxiv.org/abs/1401.3147

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.