0
$\begingroup$

Let $d$ be a fixed number. By the Cheeger theory and theory of expanders, the second smallest eigenvalue of the Laplacian for a family of $d$-regular graphs is bounded bellow by a positive constant if and only if the isoperimetric number is bounded bellow by a positive constant.

Can this be proved for any family of regular graphs (which degree of regularity of its members can be different from each other)?

$\endgroup$

1 Answer 1

1
$\begingroup$

There is a normalized version of Cheeger's inequality which uses $\mathcal{L} = \frac{\mathbf{L}}d$ as the Laplacian for $d$-regular graphs. More generally for non-regular graphs, $\mathcal L = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{1/2}$ where $\mathbf{D}$ is the degree matrix.

As seen in Chung's Spectral Graph Theory (http://www.math.ucsd.edu/~fan/research/revised.html)

$$ \frac{h_G^2}2 \le \lambda_2 \le 2 h_G $$

where $h_G$ is the Cheeger constant and $\lambda_1$ is the second smallest eigenvalue of \mathcal{L}. This is what you are looking for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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