ラマヌジャングラフ

スペクトルグラフ理論においてラマヌジャングラフは正則なグラフであって、それのテンプレート:日本語版にない記事リンクがほとんど可能な限り大きくなるものである（テンプレート:日本語版にない記事リンクをみよ）。そのようなグラフは卓越してテンプレート:仮リンク。マーティの調査報告書の中で、テンプレート:Sfnpラマヌジャングラフは「雑多な純粋数学、すなわち数論、表現論、代数幾何学が融合している」と記されている。これらのグラフは間接的にシュリニヴァーサ・ラマヌジャンに因んで命名された；それらの名称は、これらのグラフの構成を用いる、ラマヌジャン・ピーターソン予想から由来する。

定義

$G$ をつながった（テンプレート:Lang-en-short）$n$ 個の頂点をもった $d$ -正則グラフとする、そして ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ を $G$ の接続行列の固有値（もしくは $G$ のスペクトル）とする。$G$はつながった $d$ -正則グラフなので、それの固有値は、 $d={\lambda }_1>{\lambda }_2$ $\ge \cdots \ge {\lambda }_n\ge -d$ を満たす。

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

構成

固定した$d$ ごとにたいする$d$ -正則なラマヌジャングラフの構成について、数学者たちはしばしば興味をいだく。このようなラマヌジャングラフの無限な族（テンプレート:Lang-en-short）の現在の構成は、しばしば代数的である。

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

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

関連項目

• テンプレート:日本語版にない記事リンク
• テンプレート:日本語版にない記事リンク
• スペクトルグラフ理論

脚注または引用文献

雑誌

• テンプレート:Cite journal
• テンプレート:Cite journal

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• 仁平政一：「ラマヌジャングラフへの招待：群・環・体からラマヌジャングラフへ 」、プレアデス出版、ISBN 978-4-90381496-4 (2019年12月5日).