Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ where $A$ is the adjacency matrix of $G$).

If the degree is constant, we can have good expanders of course but I want to say that the lower eigenvalues cannot be too close to $1$ if the degree is constant. I was wondering if there is a quantitative statement of this sort.

Are there any bounds known about how close $\lambda_k$ can be to $1$, as a function of $k$? In particular, is something of the following form known:

``For all $ k \ll n$, we have $\lambda_k \; \leq \; \left( 1 - O\left( \frac{1}{k^{0.99}}\right) \right)$'' ?

(where the constant in the order notation can hide factors of $d$).


1 Answer 1


I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question.

For bipartite graphs for instance we can possibly get a simple first cut bound from a simple trace method. Lets look at the adjacency matrix. In your case we want to show that $\lambda_k$ is not close to 0. So consider $Trace(A^2)$. For a d-regular graph this is always $\geq dn$. Therefore $$\sum \lambda_i^2 \geq dn$$ which implies that $$2d^2k + n\lambda_k^2 \geq dn$$ Now for $k << n$ and $d$ a constant one can essentially get a $\Omega(\sqrt{d})$ bound for $\lambda_k$. So indeed they cant be very close to 1 in the normalized laplacian. I am not sure whether the parameters work out in the way you want them to.

  • $\begingroup$ I was aware of this $\sqrt{d}$ bound but I was more interested in how the eigenvalues decay with k though. Thanks anyway $\endgroup$
    – Ramprasad
    Feb 25, 2015 at 20:08

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.