probability. It is still an open problem whether there are infinitely many -regular (non-bipartite) Ramanujan graphs for any . In particular, the problem is open for , the smallest case for which is not a prime power and hence not covered by Morgenstern's construction. Ramanujan graphs as expander graphs The constant in the definition of Ramanujan graphs is asymptotically sharp. More precisely, the Alon-Boppana bound states that for every and , there exists such that all -regular graphs with at least vertices satisfy . This means that Ramanujan graphs are essentially the best possible expander graphs. Due to achieving the tight bound on , the expander mixing lemma gives excellent bounds on the uniformity of the distribution of the edges in Ramanujan graphs, and any random walks on the graphs has a logarithmic mixing time (in terms of the number of vertices): in other words, the random walk converges to the (uniform) stationary distribution very quickly. Therefore, the diameter of Ramanujan graphs are also bounded logarithmically in terms of the number of vertices. Random graphs Confirming a conjecture of Alon, Friedman showed that many families of random graphs are weakly-Ramanujan. This means that for every and and for sufficiently large , a random -regular -vertex graph satisfies with high probability. While this result shows that random graphs are close to being Ramanujan, it cannot be used to prove the existence of Ramanujan graphs. It is conjectured, though, that random graphs are Ramanujan with substantial probability (roughly 52%). In addition to direct numerical evidence, there is some theoretical support for this conjecture: the spectral gap of a -regular graph seems to behave according to a Tracy-Widom distribution from random matrix theory, which would predict the same asymptotic. Applications of Ramanujan graphs Expander graphs have many applications to computer science, number theory, and group theory, see e.g Lubotzky's survey on applications to pure and applied math and Hoory, Linial, and Wigderson's survey which focuses on computer science.. Ramanujan graphs are in some sense the best expanders, and so they are especially useful in applications where expanders are needed. Importantly, the Lubotzky, Phillips, and Sarnak graphs can be traversed extremely quickly in practice, so they are practical for applications. Some example applications include In an application to fast solvers for Laplacian linear systems, Lee, Peng, and Spielman relied on the existence of bipartite Ramanujan graphs of every degree in order to quickly approximate