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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.