Expanding graphs, Ramanujan graphs, and 1-factor perturbations (Q2381125)

This note gives a procedure for constructing infinite sequences \((X_i)_{i \in I}\) of \(k\)-regular connected simple finite graphs with increasing vertex sizes such that inf\(_{i \in I}(k - \lambda _1(X_i))\) is strictly positive, that is, expanders of degree \(k\). Here \(\lambda _0(X_i) \geq \lambda _1(X_i) \geq \cdots \geq \lambda _{n-1}(X_i)\) are the eigenvalues of the adjacency matrix of \(X_i\). For \(p\) and \(q\) distinct odd primes, the subgroup \(S_{p,q}\) of PGL\(_2(q)\) is defined and the graph \(X^{p,q}\) is specified as the Cayley graph of PGL\(_2(q)\) with respect to \(S_{p,q}\) when \(p\) is not a square modulo \(q\). \(X_{p,q}\) turns out to be a \((p+1)\)-regular bipartite connected Ramanujan graph. The desired expanders are obtained by considering \(X^{p,q}-F\) for bipartite \(X^{p,q}\), where \(F\) is a perfect matching in the graph.