Ramanujan graph convention used in the article

PDF p. 7: Section 1.3, paragraph after Remark 1.5; PDF p. 28: Section 5

Let $G=(V,E)$ be a finite undirected graph with $n=\mathrm{\mid }V\mathrm{\mid }>0$ vertices, with at most one edge between each pair and with self-loops allowed. Its adjacency matrix $A$ has $A_{xy}=1$ when $x$ and $y$ are adjacent and $0$ otherwise; a diagonal entry records a self-loop. The degree of a vertex is its row sum, so a loop counts once. Suppose $G$ is $d$-regular, meaning that every row sum is the same positive integer $d$.

Write $J$ for the all-ones matrix. In the convention used in the article, $G$ is a $d$-regular Ramanujan graph when it is an $(n,d,\alpha )$-expander for $\alpha =2\sqrt{d-1}\mathrm{/}d$: explicitly, $\mathrm{\parallel }A-(d\mathrm{/}n)J{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2\sqrt{d-1}$. Here the operator norm is induced by the Euclidean norm on ${\mathbb{C}}^V$.

Equivalently, choose an orthonormal eigenbasis of $A$ beginning with the constant unit vector $\mathbf{1}\mathrm{/}\sqrt{n}$, and call the remaining eigenvalues, counted with multiplicity, ${\lambda }_2,\dots ,{\lambda }_n$. The condition is $\mathrm{\mid }{\lambda }_i\mathrm{\mid }\le 2\sqrt{d-1}$ for every $i\ge 2$. When $n=1$ this last condition is vacuous. In particular, any additional eigenvalue $d$ and any eigenvalue $-d$ are included among the eigenvalues tested.

Adjacency, degrees, graph Laplacian, and spectral notation

Adjacency spectral expander — Definition 1.3

Regular adjacency spectra and normalized expansion

The graph convention gives a finite symmetric adjacency matrix and an unambiguous positive degree $d$ for the stated regular graph (Adjacency, degrees, graph Laplacian, and spectral notation). Since $n$ and $d$ are positive and $d$ is an integer, $2\sqrt{d-1}\mathrm{/}d$ is a well-defined nonnegative real number. The expander definition gives a well-defined centered operator norm and requires that norm to be at most $\alpha d$; substituting this value of $\alpha$ gives the displayed inequality (Adjacency spectral expander — Definition 1.3).

The regular-spectrum proposition applies because $A$ is real symmetric, nonnegative, and has every row sum equal to $d>0$. It identifies the centered norm with the largest absolute eigenvalue on the subspace orthogonal to constants, including multiplicities and any further $d$ or $-d$ eigenvalues. It also states that this norm is zero when $n=1$. Thus the eigenvalue condition is equivalent to the displayed inequality and the predicate is well defined (Regular adjacency spectra and normalized expansion).

The terminology and parameter are attributed to Expander graphs are globally synchronizing, Section 1.3 and the opening of Section 5. The spectral equivalence is justified by the separately stated proposition above.