Ramanujan graph

In the mathematical field of graph theory , Ramanujan graphs are graphs with special regularity and stability properties, which are therefore of interest in various areas of computer science and mathematics.

The graph is named after S. Ramanujan , the name of Alexander Lubotzky , Ralph Phillips and Peter Sarnak , who introduced Ramanujan graphs in 1988 (they used a result from Ramanujan).

definition

A connected - regular graph is a Ramanujan graph if all eigenvalues ​​of the adjacency matrix satisfy either or . ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda =\pm k}$ ${\displaystyle \mid \lambda \mid \leq 2{\sqrt {k-1}}}$

Ramanujan graphs can be characterized equivalently by the analogy of the Riemann conjecture for the Iharas zeta function : all poles in the area lie on the straight line . ${\displaystyle 0\leq Re(s)\leq 1}$ ${\displaystyle Re(s)={\frac {1}{2}}}$

Ramanujan graphs as optimal expander

Expander graphs are graphs with very good stability properties (i.e. they cannot be broken down into several connected components by removing relatively few edges), which are therefore of great interest in mathematics and computer science. One way to measure the expansion of a regular graph is through the second largest eigenvalue of the adjacency matrix. (The greatest eigenvalue is always for a -regular graph .) ${\displaystyle k}$ ${\displaystyle \lambda _{2}}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle k}$ ${\displaystyle \lambda _{1}=k}$

One can prove that for a -regular graph with vertices there is an inequality ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle \lambda _{2}\geq 2{\sqrt {k-1}}-o(1)}$

applies. On the other hand, it applies to Ramanujan graphs that they have almost optimal expander properties for large ones . ${\displaystyle \lambda _{2}\leq 2{\sqrt {k-1}}}$ ${\displaystyle n}$

Constructions

There are different constructions of Ramanujan graphs. For prime numbers Lubotzky-Philips-Sarnak used the Ramanujan conjecture to prove that certain quotients of the p-adic symmetric space are -regular Ramanujan graphs. Marcus-Spielman-Srivastava construct -regular Ramanujan graphs for arbitrary . ${\displaystyle p}$ ${\displaystyle PGL(2,\mathbb {Q} _{p})/PGL(2,\mathbb {Z} _{p})}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle k}$

Examples

The Petersen graph is a Ramanujan graph.

literature

• Alexander Lubotzky : Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. ISBN 3-7643-5075-X

Individual evidence

1. ↑ Alexander Lubotzky, Ralph Phillips, Peter Sarnak: Ramanujan graphs . Combinatorica 8 (1988) no. 3, 261-277. doi : 10.1007 / BF02126799 .
2. ↑ Chapter 7.3 in Lubotzky, op.cit.
3. ↑ Adam Marcus , Daniel Spielman , Nikhil Srivastava : Interlacing families I: Bipartite Ramanujan graphs of all degrees . Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. online (pdf)