<p>You might like this recent paper: <a href="http://arxiv.org/abs/1211.0589v1">http://arxiv.org/abs/1211.0589v1</a></p>

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

CC BY-SA 3.0
2012-11-11T14:40:46.077Z
2012-11-11T15:09:04.097Z
2012-11-11T15:09:04.097Z
Martin Schwarz
<p>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.)</p>

<graph-theory><co.combinatorics><spectral-graph-theory>
Bounds on the smaller eigenvalues of the adjacency matrix of a graph
Dimitris
# Bounds on the smaller eigenvalues of the adjacency matrix of a graph

(Asked by: username_0 on 2012-11-10)

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

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory


---

## 1 answers

### Answer by username_1 on 2012-11-11. Score: 7 | Accepted answer

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.


---

