Explicit constructions of Ramanujan graphs

Question

I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the adjacency matrix $A(G)$ of $G$, i.e. all its eigenvalues different from $\pm k$, are bounded by

$$ |\lambda|\leq 2\sqrt{k-1}. $$

As it is the usual case I am interested in sequences of constant degree Ramanujan graphs $\{G_{n}\}_{n\geq 1}$, i.e. all graphs $G_{n}$ are $k$-regular for some specific $k$, and that the orders $|G_{n}|$ of the graphs tend to infinity as $n$ does.

I know that the first construction of Ramanujan graphs was by Lubotzky, Philips, and Sarnak [1], which graphs were discovered independently by Margulis [2]. This construction only gives Ramanujan graphs of degree $p+1$, where $p$ is a prime number. This was generalized by Morgenstern [3] to include graphs of degrees $p^r+1$, where $p$ is a prime number. I am also aware of the construction by Pizer [4], which graphs (probably) do not arise as Cayley graphs, as was the case for the previous constructions. The latter construction also shows that the isogeny graphs arising from supersingular elliptic curves are Ramanujan. Finally, I am aware of the result of Marcus, Spielman, and Srivastava [5], where they prove the existence (though non-constructively) of (bipartite) Ramanujan graphs of all degrees, where they also mention the constructions of [6] and [7].

All the constructions I've mentioned depend on deep algebraic and number-theoretic facts, in particular the Ramanujan-Peterson Conjecture from the theory of automorphic forms and the Kazhdan's property (T) from representation theory of semi-simple Lie groups.

My questions are the following:

• Have I missed any explicit constructions? This may be a silly question, as I may have missed many that I am not aware of.
• I am also interested on existential results like that of Marcus, Spielman, and Srivastava, I've mentioned above. I am not interested however in "nearly-Ramanujan graphs", where the absolute values of non-trivial eigenvalues are bounded by $2\sqrt{k-1}+\epsilon$ for some $\epsilon>0$, like in the existential result of Friedman [8] or the construction in [9].
• Does there exist a construction that does not depend on the two aforementioned deep theorems in number theory? If there exists, is there some elementary construction like the iterative combinatorial construction of expanders by Reingold, Vadhan, and Wigderson [10]? I doubt that such elementary construction exists, so if there exists I would want to know on what it depends.

---

1. Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica 8, No. 3, 261-277 (1988). ZBL0661.05035.
2. Margulis, G. A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Probl. Inf. Transm. 24, No. 1, 39-46 (1988); translation from Probl. Peredachi Inf. 24, No. 1, 51-60 (1988). ZBL0708.05030.
3. Morgenstern, Moshe, Existence and explicit constructions of (q+1) regular Ramanujan graphs for every prime power (q), J. Comb. Theory, Ser. B 62, No. 1, 44-62 (1994). ZBL0814.68098.
4. Pizer, Arnold K., Ramanujan graphs and Hecke operators, Bull. Am. Math. Soc., New Ser. 23, No. 1, 127-137 (1990). ZBL0752.05035.
5. Marcus, Adam W.; Spielman, Daniel A.; Srivastava, Nikhil, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Ann. Math. (2) 182, No. 1, 307-325 (2015). ZBL1316.05066.
6. Jordan, Bruce W.; Livné, Ron, Ramanujan local systems on graphs, Topology 36, No. 5, 1007-1024 (1997). ZBL0872.05036.
7. Chiu, Patrick, Cubic Ramanujan graphs, Combinatorica 12, No. 3, 275-285 (1992). ZBL0770.05062.
8. Friedman, Joel, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Am. Math. Soc. 910, 100 p. (2008). ZBL1177.05070.
9. Ben-Aroya, Avraham; Ta-Shma, Amnon, A combinatorial construction of almost-Ramanujan graphs using the zig-zag product, SIAM J. Comput. 40, No. 2, 267-290 (2011). ZBL1222.05147.
10. Reingold, Omer; Vadhan, Salil; Wigderson, Avi, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. Math. (2) 155, No. 1, 157-187 (2002). ZBL1008.05101.

Answer 1

Here are some additions to your list of explicit and inexplicit Ramanujan graphs, all from the recent decade.

1. Ballantine and Ciubotaru constructed inexplicit infinite families of $(q+1,q^3+1)$-bigregular Ramanujan graphs here. See also this followup.

2. I gave inexplicit "new" infinite families of regular Ramanujan graphs (and complexes) in my paper. Specifically, applying Thm. 7.22 with $d=2$ and $D$ a division algebra that is not a field gives Ramanujan graphs that were not previously known. (A revision of this paper is forthcoming.)

3. Evra, Feigon, Maurischat and Parzanchevsky constructed explicit infinite families of $(p+1,p^3+1)$-biregular Ramanujan graphs here.

Here, the term "inexplicit" means that we can point to particular graphs and show that they are Ramanujan, but there is no known algorithm to construct these graphs (e.g. if the graphs are given as quotients of an infinite tree by a particular infinite group). "Explicit" means that there is moreover an efficient algorithm to construct the graphs.

All of these results rely on known cases of the Ramanujan--Petersson conjecture.