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.)
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
