Explicit expanders of every degree and size (Q2236654)

An \((n,d,\lambda)\)-graph is a \(d\)-regular graph on \(n\) vertices all of whose eigenvalues (i.e. the eigenvalues of its adjacency matrix) other than \(d\) have modulus at most \(\lambda\). Such graphs are known to have good expanding and pseudo-random properties. The smaller \(\lambda\) can be got the better the expansion properties are. It is well known that we must have \(\lambda \geq 2\sqrt{d-1}-O(1/\log(n)^{2})\) so there is interest in getting \((n,d,\lambda)\) graphs with \(\lambda\) as small as possible. An \((n,d,\lambda)\)-graph is said to be Ramanujan if \(\lambda\leq 2\sqrt{d-1}\). \textit{A. Lubotzky} et al. [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)] and independently \textit{G. A. Margulis} [Probl. Inf. Transm. 24, No. 1, 39--46 (1988; Zbl 0708.05030); translation from Probl. Peredachi Inf. 24, No. 1, 51--60 (1988)] constructed infinite families of Ramanujan graphs of degree \(d\) and \textit{J. Friedman} [A proof of Alon's second eigenvalue conjecture and related problems. Providence, RI: American Mathematical Society (AMS) (2008; Zbl 1177.05070)] showed that a random \(d\)-regular graph on \(n\) vertices is \((n,d,\lambda)\) for \(\lambda=2\sqrt{d-1}+o(1)\). However it is often desirable to be able to specify the number of vertices and degrees, and it is also desirable that the constructions should be explicit: we shall say that a construction is explicit if there is a deterministic polynomial-time algorithm which, given \(n\) and \(d\), outputs an \((n,d,\lambda)\) graph. It is strongly explicit if further the adjacency list of any vertex can be produced in time polylogarithmic in \(n\). \par The important paper under review has three main theorems filling in gaps in the earlier work. Firstly, it shows that, for every \(d\), there is a strongly explicit construction of \((n,d,\lambda)\)-graphs with \(\lambda \leq (2+o_{d}(1)) \sqrt{d}\) where the \(o_{d}(1)\) term tends to 0 as \(d\rightarrow\infty\) and the possible values of \(n\) form a sequence in which the ratio of consecutive terms tends to 1. The comparatively straightforward proof of this fact, less refined versions of which have been circulating informally for some time, is based on packing certain known Ramanujan graphs, which are Cayley graphs of the same group. \par The second main result is that for any prime number congruent to 1 modulo 4 and every large enough \(n\), there is a strongly explicit construction of an \((n,d,\lambda)\) graph on exactly \(n\) vertices with \(d=p+2\) and \(\lambda \leq (1+\sqrt{2})\sqrt{d-1}+o(1)\) (in fact a slightly more refined result is proved). The proof starts from a given Ramanujan graph by adding vertices (and edges to preserve regularity) and then estimating the eigenvalues using the variational principle. \par The third main result is an explicit (rather than strongly explicit) construction. For every degree \(d\), every \(\epsilon>0\) and every large enough \(n\geq n_{0}(d,\epsilon)\), provided the obvious handshake lemma constraint that \(nd\) is even holds, there is an explicit construction of an \((n,d,\lambda)\)-graph with \(\lambda \leq 2\sqrt{d-1}+\epsilon\). The rough idea here is to take a known near-Ramanujan graph and to remove carefully chosen vertices and insert matchings to maintain regularity. Checking that this works involves a result on delocalisation of the eigenvectors (crudely speaking, the idea that the normalised eigenvectors should be roughly uniformly distributed on the unit sphere) which in turn depends on the absence of short cycles in the neighbourhoods of the removed vertices.