Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 7 down vote accepted

You might like this recent paper:

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.

share|cite|improve this answer
This is a very interesting work. Thank you! – Dimitris Nov 13 '12 at 14:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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