Раманұжан графтары: қасиеттері мен құрылысы

In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

Let be a connected regular graph with vertices, and let be the eigenvalues of the adjacency matrix of (or the spectrum of ). Because is connected and regular, its eigenvalues satisfy
Define A connected regular graph is a Ramanujan graph if
Many sources uses an alternative definition (whenever there exists with ) to define Ramanujan graphs. In other words, we allow in addition to the "small" eigenvalues. Since if and only if the graph is bipartite, we will refer to the graphs that satisfy this alternative definition but not the first definition bipartite Ramanujan graphs. If is a Ramanujan graph, then is a bipartite Ramanujan graph, so the existence of Ramanujan graphs is stronger. As observed by Toshikazu Sunada, a regular graph is Ramanujan if and only if its Ihara zeta function satisfies an analog of the Riemann hypothesis.

The complete graph has spectrum , and thus and the graph is a Ramanujan graph for every The complete bipartite graph has spectrum and hence is a bipartite Ramanujan graph for every The Petersen graph has spectrum , so it is a 3 regular Ramanujan graph. The icosahedral graph is a 5 regular Ramanujan graph. A Paley graph of order is regular with all other eigenvalues being , making Paley graphs an infinite family of Ramanujan graphs. More generally, let be a degree 2 or 3 polynomial over Let be the image of as a multiset, and suppose Then the Cayley graph for with generators from is a Ramanujan graph. Mathematicians are often interested in constructing infinite families of regular Ramanujan graphs for every fixed Such families are useful in applications.

Several explicit constructions of Ramanujan graphs arise as Cayley graphs and are algebraic in nature. See Winnie Li's survey on Ramanujan's conjecture and other aspects of number theory relevant to these results. Lubotzky, Phillips and Sarnak showed how to construct an infinite family of regular Ramanujan graphs, whenever is a prime number and Both proofs use the Ramanujan conjecture, which led to the name of Ramanujan graphs. Besides being Ramanujan graphs, these constructions satisfies some other properties, for example, their girth is where is the number of nodes. Let us sketch the Lubotzky Phillips Sarnak construction. Let be a prime not equal to By Jacobi's four square theorem, there are solutions to the equation where is odd and are even. To each such solution associate the matrix If is not a quadratic residue modulo let be the Cayley graph of with these generators, and otherwise, let be the Cayley graph of with the same generators. Then is a regular graph on or vertices depending on whether or not is a quadratic residue modulo It is proved that is a Ramanujan graph. Morgenstern later extended the construction of Lubotzky, Phillips and Sarnak. His extended construction holds whenever is a prime power. Arnold Pizer proved that the supersingular isogeny graphs are Ramanujan, although they tend to have lower girth than the graphs of Lubotzky, Phillips, and Sarnak. Like the graphs of Lubotzky, Phillips, and Sarnak, the degrees of these graphs are always a prime number plus one.

Adam Marcus, Daniel Spielman and Nikhil Srivastava proved the existence of infinitely many regular bipartite Ramanujan graphs for any Later they proved that there exist bipartite Ramanujan graphs of every degree and every number of vertices. Michael B. Cohen showed how to construct these graphs in polynomial time. The initial work followed an approach of Bilu and Linial. They considered an operation called a 2 lift that takes a regular graph with vertices and a sign on each edge, and produces a new regular graph on vertices. Bilu & Linial conjectured that there always exists a signing so that every new eigenvalue of has magnitude at most This conjecture guarantees the existence of Ramanujan graphs with degree and vertices for any —simply start with the complete graph , and iteratively take 2 lifts that retain the Ramanujan property. Using the method of interlacing polynomials, Marcus, Spielman, and Srivastava extended the original work of Marcus, Spielman and Srivastava to r lifts. 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.

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.

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.