Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

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

Your Answer

 
discard

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.