Are there any known (non-trivial) bounds (combinatorial in nature, based on poly-time computable properties of a graph) on the third, down to the smallest, eigenvalue of an (un-weighted) adjacency matrix? For example we know that the largest eigenvalue admits the following bounds $$\max(\sqrt{d_{\max}}, d_{\text{ave}})\le \lambda_{\max}=\lambda_1 \le d_{\max}$$ Anything of the above flavor for $\lambda_i$, $i\ge 3$? (Given that these can be negative, (lower) bounding $|\lambda_i|$ might seem more appealing.)


1 Answer 1


You might like this recent paper: http://arxiv.org/abs/1211.0589v1

The paper shows, e.g., that "for any finite graph with $n$ vertices and all $k ≥ 2$, the $k$th largest eigenvalue" of the graph's Laplacian, i.e. $L=I-A/d$, "is at most $1−\Omega(\frac{k^3}{n^3})$", where $A$ is the adjacency matrix and $d$ a bound on the degree.


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.