<p>At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq CL_G$ for $t$ the smallest real number such that $L_G \preceq tL_H$. (I.e. $t := \|L_H^{-1/2} L_G L_H^{-1/2}\|$ where the norm is the operator norm and inverses are taken w.r.t. to the space orthogonal to the all-ones vector). The eigenvalues of $L_{K_{n,n}}$ are $\lambda_1 = 0, \lambda_2 = \ldots \lambda_{2n-1} = n, \lambda_{2n} = 2n$. For any $d$-regular bipartite $H$, the eigenvalues $0=\mu_1 \le \ldots \le \mu_{2n} = 2d$  of $L_H$ come in pairs $d \pm x$. By Alon-Boppana, $\mu_2 \le d-2\sqrt{d-1}$, and, therefore, $\mu_{2d-1} \geq d + 2\sqrt{d-1}$ (ignoring lower-order terms). This implies $C \geq \frac{d + 2\sqrt{d-1}}{d - 2\sqrt{d-1}}$, which is achived by a $d$-regular Ramanujan graph.</p>

CC BY-SA 3.0
2015-09-24T17:30:48.680Z
2015-09-24T17:30:48.680Z
Sasho Nikolov
<p>The Ramanujan graphs are optimal from the Alon-Bopanna point of view but..</p>

<ol>
<li><p>Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : <a href="http://arxiv.org/pdf/0808.0163v3.pdf" rel="nofollow">http://arxiv.org/pdf/0808.0163v3.pdf</a> ) </p>

<p>(..At least w.r.t $K_n$ can one say that given any $d$ and $n$, any $d-$regular Ramanujan graph on $n$ vertices, say $R_{(d,n)}$, gives the smallest $a$ s.t $x^T L_{K_{n}}x \leq \frac{n}{d} x^TL_{R_{(d,n)}}x \leq a x^TL_{K_{n} }x , \forall x \in \mathbb{R}^n$?..or some such similar inequality?.. ) </p></li>
<li><p>Does the usual Cheeger's inequality become sharper if restricted to Ramanujan graphs? Or do we otherwise know of graphs which either saturate the Cheeger's inequality and/or maximize any of the combinatorial notions of expansion? </p>

<p>The only kind of connection I know of between the spectral gap of an expander to its combinatorial expansion are statements like Theorem 4 and 6 here in these notes, <a href="http://www.math.rutgers.edu/~sk1233/courses/graphtheory-F11/expander1.pdf" rel="nofollow">http://www.math.rutgers.edu/~sk1233/courses/graphtheory-F11/expander1.pdf</a>. But even this is a lower bound and not an upperbound. One can put in $\lambda = 2\sqrt{d-1}$ in these two theorems but that somehow looks too weak and naive. </p>

<p>I wonder if something sharper can be said about the combinatorial expansion properties of a Ramanujan expander : may be some sense in which one can justify calling them optimal from this point of view too? </p></li>
</ol>

<hr>

<ul>
<li><p>Lets say we use the definition of Ramanujan graph as those $d-$regular graphs all of whose  adjacency eigenvalues are of magnitude $\leq 2\sqrt{d-1}$ except the largest and the smallest.</p></li>
<li><p>For Cheeger's Inequality lets use the form as in these notes, <a href="http://www.eecs.berkeley.edu/~luca/books/expanders.pdf" rel="nofollow">http://www.eecs.berkeley.edu/~luca/books/expanders.pdf</a>, i.e for a $d-$regular graph,</p></li>
</ul>

<p>$$ \frac { \lambda_{1+min}(I - \frac{1}{d}A )}{2 } \leq \phi(G) = min _{ S \subset V, \vert S \vert \leq \frac{\vert V \vert}{2} } \frac {\vert \partial S \vert }{d \vert S \vert }  \leq \sqrt {2\lambda_{1+min}(I - \frac{1}{d}A )}$$  </p>

<cc.complexity-theory><graph-theory><spectral-graph-theory><expanders><spectral>
About some possible optimality properties of Ramanujan graphs
Student
# About some possible optimality properties of Ramanujan graphs

(Asked by: username_0 on 2015-09-21)

The Ramanujan graphs are optimal from the Alon-Bopanna point of view but..

1. Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : <http://arxiv.org/pdf/0808.0163v3.pdf> )

   (..At least w.r.t $K\_n$ can one say that given any $d$ and $n$, any $d-$regular Ramanujan graph on $n$ vertices, say $R\_{(d,n)}$, gives the smallest $a$ s.t $x^T L\_{K\_{n}}x \leq \frac{n}{d} x^TL\_{R\_{(d,n)}}x \leq a x^TL\_{K\_{n} }x , \forall x \in \mathbb{R}^n$?..or some such similar inequality?.. )
2. Does the usual Cheeger's inequality become sharper if restricted to Ramanujan graphs? Or do we otherwise know of graphs which either saturate the Cheeger's inequality and/or maximize any of the combinatorial notions of expansion?

   The only kind of connection I know of between the spectral gap of an expander to its combinatorial expansion are statements like Theorem 4 and 6 here in these notes, <http://www.math.rutgers.edu/~sk1233/courses/graphtheory-F11/expander1.pdf>. But even this is a lower bound and not an upperbound. One can put in $\lambda = 2\sqrt{d-1}$ in these two theorems but that somehow looks too weak and naive.

   I wonder if something sharper can be said about the combinatorial expansion properties of a Ramanujan expander : may be some sense in which one can justify calling them optimal from this point of view too?

---

* Lets say we use the definition of Ramanujan graph as those $d-$regular graphs all of whose adjacency eigenvalues are of magnitude $\leq 2\sqrt{d-1}$ except the largest and the smallest.
* For Cheeger's Inequality lets use the form as in these notes, <http://www.eecs.berkeley.edu/~luca/books/expanders.pdf>, i.e for a $d-$regular graph,

$$ \frac { \lambda\_{1+min}(I - \frac{1}{d}A )}{2 } \leq \phi(G) = min \_{ S \subset V, \vert S \vert \leq \frac{\vert V \vert}{2} } \frac {\vert \partial S \vert }{d \vert S \vert } \leq \sqrt {2\lambda\_{1+min}(I - \frac{1}{d}A )}$$

**Tags:** cc.complexity-theory, graph-theory, spectral-graph-theory, expanders, spectral

---

## 1 answers

### Answer by username_1 on 2015-09-24. Score: 4

At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL\_H \preceq CL\_G$ for $t$ the smallest real number such that $L\_G \preceq tL\_H$. (I.e. $t := \|L\_H^{-1/2} L\_G L\_H^{-1/2}\|$ where the norm is the operator norm and inverses are taken w.r.t. to the space orthogonal to the all-ones vector). The eigenvalues of $L\_{K\_{n,n}}$ are $\lambda\_1 = 0, \lambda\_2 = \ldots \lambda\_{2n-1} = n, \lambda\_{2n} = 2n$. For any $d$-regular bipartite $H$, the eigenvalues $0=\mu\_1 \le \ldots \le \mu\_{2n} = 2d$ of $L\_H$ come in pairs $d \pm x$. By Alon-Boppana, $\mu\_2 \le d-2\sqrt{d-1}$, and, therefore, $\mu\_{2d-1} \geq d + 2\sqrt{d-1}$ (ignoring lower-order terms). This implies $C \geq \frac{d + 2\sqrt{d-1}}{d - 2\sqrt{d-1}}$, which is achived by a $d$-regular Ramanujan graph.


---

