# Upper bounds on higher order eigenvalues of regular graphs

Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ where $A$ is the adjacency matrix of $G$).

If the degree is constant, we can have good expanders of course but I want to say that the lower eigenvalues cannot be too close to $1$ if the degree is constant. I was wondering if there is a quantitative statement of this sort.

Are there any bounds known about how close $\lambda_k$ can be to $1$, as a function of $k$? In particular, is something of the following form known:

For all $k \ll n$, we have $\lambda_k \; \leq \; \left( 1 - O\left( \frac{1}{k^{0.99}}\right) \right)$'' ?

(where the constant in the order notation can hide factors of $d$).

For bipartite graphs for instance we can possibly get a simple first cut bound from a simple trace method. Lets look at the adjacency matrix. In your case we want to show that $\lambda_k$ is not close to 0. So consider $Trace(A^2)$. For a d-regular graph this is always $\geq dn$. Therefore $$\sum \lambda_i^2 \geq dn$$ which implies that $$2d^2k + n\lambda_k^2 \geq dn$$ Now for $k << n$ and $d$ a constant one can essentially get a $\Omega(\sqrt{d})$ bound for $\lambda_k$. So indeed they cant be very close to 1 in the normalized laplacian. I am not sure whether the parameters work out in the way you want them to.
• I was aware of this $\sqrt{d}$ bound but I was more interested in how the eigenvalues decay with k though. Thanks anyway – Ramprasad Feb 25 '15 at 20:08