<p>I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question. </p>

<p>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 &lt;&lt; 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. </p>

CC BY-SA 3.0
2015-02-25T20:08:07.860Z
I was aware of this $\sqrt{d}$ bound but I was more interested in how the eigenvalues decay with k though. Thanks anyway
Ramprasad
CC BY-SA 3.0
2015-02-25T14:21:52.747Z
2015-02-25T14:29:03.807Z
2015-02-25T14:29:03.807Z
NAg
<p>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$). </p>

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

<p>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:</p>

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

<p>(where the constant in the order notation can hide factors of $d$).</p>

<spectral-graph-theory>
Upper bounds on higher order eigenvalues of regular graphs
Ramprasad
# Upper bounds on higher order eigenvalues of regular graphs

(Asked by: username_0 on 2015-02-24)

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

**Tags:** spectral-graph-theory

---

## 1 answers

### Answer by username_1 on 2015-02-25. Score: 1

I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question.

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.

> **Comments:**
> **username_0**: I was aware of this $\sqrt{d}$ bound but I was more interested in how the eigenvalues decay with k though. Thanks anyway  

---

