Lubotzky–Phillips–Sarnak Ramanujan Graphs

The Lubotzky–Phillips–Sarnak (LPS) construction (Lubotzky et al., 1988) provides explicit $(p+1)$-regular Ramanujan graphs $X^{p,q}$ for primes $p, q \equiv 1 \pmod 4$ with $p \neq q$. It was the first explicit construction of Ramanujan graphs, with the spectral bound ultimately resting on Deligne's proof (see (Deligne, 2006)) of the Ramanujan–Petersson conjecture. Together with Morgenstern's construction for even prime powers (see Morgenstern Ramanujan Graphs), it gives this package explicit optimal spectral expanders over a wide range of degrees which are objects of independent interest in graph theory, derandomization, and classical coding theory, usable entirely on their own without any of the quantum stuff in this package.

Construction

By Jacobi's four-square theorem, there are exactly $p + 1$ integer solutions $(a_0, a_1, a_2, a_3)$ of

\[p = a_0^2 + a_1^2 + a_2^2 + a_3^2\]

with $a_0 > 0$ odd and $a_1, a_2, a_3$ even. Each solution is mapped to the matrix

\[\begin{pmatrix} a_0 + i a_1 & a_2 + i a_3 \\ -a_2 + i a_3 & a_0 - i a_1 \end{pmatrix} \in \mathrm{PGL}_2(\mathbb{F}_q),\]

where $i$ is a square root of $-1$ in $\mathbb{F}_q$. The graph $X^{p,q}$ is the Cayley graph generated by these $p+1$ elements, and its structure depends on the Legendre symbol $\left(\frac{p}{q}\right)$:

• $\left(\frac{p}{q}\right) = 1$: the generators lie in $\mathrm{PSL}_2(\mathbb{F}_q)$, and $X^{p,q}$ is a non-bipartite graph on $|X^{p,q}| = q(q^2-1)/2$ vertices.
• $\left(\frac{p}{q}\right) = -1$: $X^{p,q}$ is a bipartite Cayley graph of $\mathrm{PGL}_2(\mathbb{F}_q)$ on $|X^{p,q}| = q(q^2-1)$ vertices.

The graph is constructed with LPS.

Example: $p = 13,\ q = 17$

Here we construct the LPS Ramanujan graph $X^{13,17}$ and verify the properties established on page 263 of (Lubotzky et al., 1988). Since $\left(\frac{13}{17 \right) = 1$, this is the non-bipartite case (case ii), a $14$-regular graph on $|\mathrm{PSL}_2(\mathbb{F}_{17})| = 2448$ vertices.

julia> using QuantumExpanders, Oscar, LinearAlgebra;

julia> using Graphs: degree, vertices, nv, ne, is_bipartite, adjacency_matrix, diameter, is_connected, independent_set, has_edge, MaximalIndependentSet, greedy_color;

julia> using GraphsColoring: DSATUR, color, Greedy;

julia> using NautyGraphs: NautyGraph, is_isomorphic;
 
julia> p = 13; q = 17;
 
julia> legendre_symbol(p, q)
1
 
julia> X = LPS(p, q);
 
julia> n = q*(q^2 - 1)÷2
2448

$(p+1)$-regularity, order, and connectivity

julia> all(degree(X, v) == p + 1 for v in vertices(X))
true
 
julia> nv(X) == n
true
 
julia> is_connected(X)
true

Ramanujan bound

The trivial eigenvalue is $p + 1$, and every other eigenvalue $\mu$ satisfies $|\mu| \leq 2\sqrt{p}$:

julia> λs = sort(real.(eigvals(Matrix(adjacency_matrix(X)))), rev=true);
 
julia> λs[1] ≈ p + 1
true
 
julia> all(abs(μ) ≤ 2√p + 1e-10 for μ in λs[2:end])
true

The same check is available as a convenience predicate:

julia> is_ramanujan(X, p)
true

Non-bipartiteness

Since $\left(\frac{p}{q}\right) = 1$, the graph is non-bipartite:

julia> is_bipartite(X)
false

Girth bound (case ii (a))

The girth satisfies $g(X^{p,q}) \geq 2\log_p q$:

julia> using IGraphs: IGraph, IGVectorInt, LibIGraph;
 
julia> girth_lower_bound = floor(Int, 2*log(p, q));
 
julia> g_igraph = IGraph(X); girth_val = Ref{LibIGraph.igraph_real_t}(0.0); cycle = IGVectorInt();
 
julia> LibIGraph.igraph_girth(g_igraph.objref, girth_val, cycle.objref);
 
julia> Int(girth_val[]) >= girth_lower_bound
true

Diameter bound (case ii (b))

The diameter satisfies $\mathrm{diam}(X^{p,q}) \leq 2\log_p n + 2\log_p 2 + 1$:

julia> diameter(X) ≤ ceil(Int, 2*log(p, n) + 2*log(p, 2) + 1)
true

Independence number (case ii (c))

The independence number satisfies $i(X^{p,q}) \leq \frac{2\sqrt{p}}{p+1}\, n$:

julia> ind_set = independent_set(X, MaximalIndependentSet());
 
julia> length(ind_set) ≤ ceil(Int, (2√p/(p + 1))*n)
true

The bipartite case

When $\left(\frac{p}{q}\right) = -1$, the graph $X^{p,q}$ is instead the bipartite Cayley graph of $\mathrm{PGL}_2(\mathbb{F}_q)$ on $q(q^2-1)$ vertices, satisfying the corresponding case i bounds of (Lubotzky et al., 1988): the girth improves to

\[g(X^{p,q}) \geq 4\log_p q - \log_p 4,\]

while the diameter bound $\mathrm{diam}(X^{p,q}) \leq 2\log_p n + 2\log_p 2 + 1$ is the same as in the non-bipartite case.

References