About some possible optimality properties of Ramanujan graphs

Question

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

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.