ラマヌジャングラフ

${\displaystyle G}$ をつながった（英: connected）${\displaystyle n}$ 個の頂点をもった ${\displaystyle d}$ -正則グラフとする、そして ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ を ${\displaystyle G}$ の接続行列の固有値（もしくは ${\displaystyle G}$ のスペクトル）とする。${\displaystyle G}$はつながった ${\displaystyle d}$ -正則グラフなので、それの固有値は、 ${\displaystyle d=\lambda _{1}>\lambda _{2}}$ ${\displaystyle \geq \cdots \geq \lambda _{n}\geq -d}$ を満たす。

${\displaystyle \lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,|\lambda _{n}|)}$ と定義する。もし ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$ を満たすならば、 ${\displaystyle d}$ -正則グラフは ラマヌジャングラフ である。

固定した${\displaystyle d}$ ごとにたいする${\displaystyle d}$ -正則なラマヌジャングラフの構成について、数学者たちはしばしば興味をいだく。このようなラマヌジャングラフの無限な族（英: infinite family）の現在の構成は、しばしば代数的である。

• ${\displaystyle p}$ が素数で、${\displaystyle 4}$ を法として${\displaystyle 1}$ と合同な場合に、ルボツキー、フィリップス、サルナック^[2]は、${\displaystyle (p+1)}$ -正則ラマヌジャングラフの或る無限な族をどうやって構成するかを示した。ラマヌジャングラフの呼称を由来させる、ラマヌジャン・ピーターソン予想を、彼らの証明は用いる。ラマヌジャングラフであることに加えて、彼らの構成は幾つかの性質を満たす、たとえば、${\displaystyle n}$ をその辺の数として、それらの内周は${\displaystyle \Omega (\log _{p}(n))}$ である。
• モルゲンシュテルン^[3]はルボツキー、フィリップス、サルナックの構成を ${\displaystyle p}$ が素数の冪の場合に拡張した。

任意の${\displaystyle d>3}$ について、幾つかの無限な（2部（英: bipartite）でない）${\displaystyle d}$ -正則なラマヌジャングラフが存在するかどうかは、未解決である。特に、${\displaystyle d-1}$ が素数の冪でなくモルゲンシュテルンの構成でカバーされない最小の場合である ${\displaystyle d=7}$ についても未解決である。