ラマヌジャングラフ

数学のスペクトルグラフ理論の分野において、ラマヌジャングラフは、スペクトルギャップがほぼ最大になる正則グラフです（極値グラフ理論を参照）。このようなグラフは、優れたスペクトル拡張器です。Murtyの調査論文^{[1]で指摘されているように、ラマヌジャングラフは「純粋数学のさまざまな分野、つまり}数論、表現論、代数幾何学を融合したもの」です。これらのグラフは間接的にシュリニヴァーサ・ラマヌジャンにちなんで名付けられています。その名前は、これらのグラフの一部の構築に使用された ラマヌジャン-ピーターソン予想に由来しています。

を頂点を持つ連結された-正則グラフとし、を の隣接行列(またはのスペクトル)の固有値とします。は連結かつ-正則であるため、その固有値は を満たします。 ${\displaystyle G}$${\displaystyle d}$${\displaystyle n}$${\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}|,\ldots ,|\lambda _{n}|)}$${\displaystyle d}$${\displaystyle G}$${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$

多くの情報源では、ラマヌジャン グラフを定義するために代替定義 ( が存在する場合) を使用しています。[ ^2]言い換えると、「小さな」固有値に加えて を許可します。グラフが二部 である場合に限り、この代替定義を満たすグラフを参照しますが、最初の定義である二部ラマヌジャン グラフは参照しません。 がラマヌジャン グラフである場合、 は二部ラマヌジャン グラフであるため、ラマヌジャン グラフの存在はより強くなります。 ${\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|}$${\displaystyle \lambda _{i}}$${\displaystyle |\lambda _{i}|<d}$${\displaystyle -d}$${\displaystyle \lambda _{n}=-d}$${\displaystyle G}$${\displaystyle G\times K_{2}}$

砂田俊一が観察したように、正則グラフがラマヌジャングラフであるためには、その伊原ゼータ関数がリーマン予想の類似物を満たす必要がある。^[3]

• 完全グラフは スペクトル を持つため、グラフは任意の に対してラマヌジャン グラフになります。完全二部グラフはスペクトル を持つため、グラフは任意の に対して二部ラマヌジャン グラフになります。${\displaystyle K_{d+1}}$${\displaystyle d,-1,-1,\dots ,-1}$${\displaystyle \lambda (K_{d+1})=1}$${\displaystyle d>1}$ ${\displaystyle K_{d,d}}$${\displaystyle d,0,0,\dots ,0,-d}$${\displaystyle d}$
• ピーターセングラフはスペクトルを持つので、3正則ラマヌジャングラフである。二十面体グラフは5正則ラマヌジャングラフである。^[4]${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$
• 順序 のペイリーグラフは -正則で、他のすべての固有値は であるため、ペイリーグラフはラマヌジャングラフの無限族になります。${\displaystyle q}$${\displaystyle {\frac {q-1}{2}}}$${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$
• より一般的には、を 上の 2 次または 3 次多項式とします。を の多重集合としての像とし、 と仮定します。すると、からの生成元を持つのケーリー グラフはラマヌジャン グラフになります。${\displaystyle f(x)}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle S=\{f(x)\,:\,x\in \mathbb {F} _{q}\}}$${\displaystyle f(x)}$${\displaystyle S=-S}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle S}$

数学者は、任意の固定された に対して -正則ラマヌジャン グラフの無限族を構築することにしばしば興味を持っています。このような族はアプリケーションで役立ちます。 ${\displaystyle d}$${\displaystyle d}$

ラマヌジャングラフの明示的な構成のいくつかはケイリーグラフとして現れ、本質的に代数的です。ラマヌジャン予想とこれらの結果に関連する数論の他の側面に関するWinnie Liの調査を参照してください。^[5]

Lubotzky、Phillips、Sarnak ^[2]およびMargulis ^{[6]はそれぞれ独立に、 が}素数で のときに、 -正則ラマヌジャン グラフの無限族を構築する方法を示しました。どちらの証明もラマヌジャン予想 を使用し、これがラマヌジャン グラフの名前の由来となっています。ラマヌジャン グラフであることに加えて、これらの構築は他のいくつかの特性も満たします。たとえば、その内周は で、 はノードの数です。 ${\displaystyle (p+1)}$${\displaystyle p}$${\displaystyle p\equiv 1{\pmod {4}}}$${\displaystyle \Omega (\log _{p}(n))}$${\displaystyle n}$

Lubotzky-Phillips-Sarnak 構成を概観しましょう。を と等しくない素数とします。ヤコビの四平方定理により、が奇数で が偶数である方程式 の解が存在します。このような各解に、行列を関連付けます。 が を法とする平方剰余でない場合は、をこれらの生成元を持つのケイリー グラフとし、そうでない場合は、を同じ生成元を持つのケイリー グラフとします。すると、 は を法とする平方剰余であるかどうかによって、 または頂点上の -正則グラフになります。 がラマヌジャン グラフである ことが証明されています。${\displaystyle q\equiv 1{\bmod {4}}}$${\displaystyle p}$${\displaystyle p+1}$${\displaystyle p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}$${\displaystyle a_{0}>0}$${\displaystyle a_{1},a_{2},a_{3}}$${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$$${\displaystyle {\tilde {\alpha }}={\begin{pmatrix}a_{0}+ia_{1}&a_{2}+ia_{3}\\-a_{2}+ia_{3}&a_{0}-ia_{1}\end{pmatrix}},\qquad i{\text{ a fixed solution to }}i^{2}=-1{\bmod {q}}.}$$${\displaystyle p}$${\displaystyle q}$${\displaystyle X^{p,q}}$${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$${\displaystyle p+1}$${\displaystyle X^{p,q}}$${\displaystyle \operatorname {PSL} (2,\mathbb {Z} /q\mathbb {Z} )}$${\displaystyle X^{p,q}}$${\displaystyle (p+1)}$${\displaystyle n=q(q^{2}-1)}$${\displaystyle q(q^{2}-1)/2}$${\displaystyle p}$${\displaystyle q}$${\displaystyle X^{p,q}}$

モルゲンシュテルン^[7]は後にルボツキー、フィリップス、サルナクの構成を拡張した。彼の拡張された構成は、が素数冪であるときはいつでも成り立つ。 ${\displaystyle p}$

アーノルド・パイザーは、超特異同体グラフはラマヌジャンのグラフであることを証明したが、ルボツキー、フィリップス、サーナックのグラフよりも内周が低い傾向がある。^[8]ルボツキー、フィリップス、サーナックのグラフと同様に、これらのグラフの次数は常に素数プラス1である。

アダム・マーカス、ダニエル・スピルマン、ニキル・スリヴァスタヴァ^[9]は、任意のに対して無限個の-正則二部ラマヌジャングラフが存在することを証明した。後に^[10]彼らは、あらゆる次数とあらゆる頂点数の二部ラマヌジャングラフが存在することを証明した。マイケル・B・コーエン^[11]は、これらのグラフを多項式時間で構築する方法を示した。 ${\displaystyle d}$${\displaystyle d\geq 3}$

初期の研究は Bilu とLinialのアプローチを踏襲しました。彼らは、各辺に頂点と符号を持つ -正則グラフを取り、頂点上に新しい -正則グラフを生成する 2-リフトと呼ばれる操作を検討しました。BiluとLinial は、 のすべての新しい固有値の大きさが最大で になるように、常に符号が存在すると予想しました。この予想は、任意の に対して次数と頂点を持つラマヌジャン グラフの存在を保証します。完全なグラフ から始めて、ラマヌジャン特性を保持する 2-リフトを反復的に実行します。 ${\displaystyle d}$${\displaystyle G}$${\displaystyle n}$${\displaystyle d}$${\displaystyle G'}$${\displaystyle 2n}$${\displaystyle G'}$${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle d}$${\displaystyle 2^{k}(d+1)}$${\displaystyle k}$${\displaystyle K_{d+1}}$

^{マーカス、スピルマン、スリヴァスタヴァ[9]は}、多項式をインターレースする方法を使用して、がすでに二部ラマヌジャングラフである場合にビルーとリニアルの予想が成り立つことを証明しました。これは存在結果を結論付けるのに十分です。続編^[10]は、ランダムな二部マッチングの合計がゼロでない確率でラマヌジャンであるというより強い主張を証明しました。ホール、プーダー、サウィン^[12]は、マーカス、スピルマン、スリヴァスタヴァの元の研究をrリフトに拡張しました。 ${\displaystyle G}$${\displaystyle d}$

任意の に対して -正則（非二部）ラマヌジャングラフが無限に存在するかどうかは、まだ未解決の問題です。特に、 に対しては未解決の問題であり、 の最小のケースは素数冪ではなく、したがってモルゲンシュテルンの構成ではカバーされません。 ${\displaystyle d}$${\displaystyle d\geq 3}$${\displaystyle d=7}$${\displaystyle d-1}$

ラマヌジャン グラフの定義における定数は、漸近的に鋭い。より正確には、アロン-ボッパナ境界は、任意の および に対して、少なくとも の頂点を持つすべての-正則グラフがを満たすような が存在することを述べています。これは、ラマヌジャン グラフが本質的に最良の拡張グラフであることを意味します。 ${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle d}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle d}$${\displaystyle G}$${\displaystyle n}$${\displaystyle \lambda (G)>2{\sqrt {d-1}}-\epsilon }$

の厳密な境界を達成することにより、エキスパンダー混合補題はラマヌジャングラフの辺の分布の均一性に優れた境界を与え、グラフ上の任意のランダムウォークは（頂点の数に関して）対数混合時間を持ちます。言い換えると、ランダムウォークは（均一な）定常分布に非常に速く収束します。したがって、ラマヌジャングラフの直径も頂点の数に関して対数的に制限されます。 ${\displaystyle \lambda (G)}$

アロンの予想を確認し、フリードマン^{[13] は、}ランダムグラフの多くの族が弱ラマヌジャンであることを示した。これは、すべてのおよびに対して、十分に大きい に対して、ランダム-正則-頂点グラフは高い確率で を満たすことを意味する。この結果はランダムグラフがラマヌジャンに近いことを示しているが、ラマヌジャングラフの存在を証明するために使用することはできません。しかし、^[14]では、ランダムグラフは相当な確率 (およそ 52%) でラマヌジャンであると予想されています。直接的な数値的証拠に加えて、この予想を裏付ける理論的な裏付けもあります。 -正則グラフのスペクトルギャップは、ランダム行列理論からのTracy-Widom 分布に従って動作するように見え 、同じ漸近線を予測します。 ${\displaystyle d}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle d}$${\displaystyle n}$${\displaystyle G}$${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$${\displaystyle d}$

エクスパンダー グラフは、コンピューター サイエンス、数論、群論に多くの応用があります。たとえば、純粋数学と応用数学への応用に関する Lubotzky の調査や、コンピューター サイエンスに焦点を当てた Hoory、Linial、Wigderson の調査を参照してください。ラマヌジャン グラフは、ある意味、最高のエクスパンダーであるため、エクスパンダーが必要なアプリケーションで特に役立ちます。重要なのは、Lubotzky、Phillips、Sarnak グラフは実際には非常に高速にトラバースできるため、アプリケーションに実用的であるということです。

いくつかのアプリケーション例には以下が含まれます

• ラプラシアン線形システムの高速ソルバーへの応用において、リー、ペン、スピルマン^[15]は、完全なグラフを素早く近似するために、あらゆる次数の二部ラマヌジャングラフの存在に依存した。
• ルベツキーとペレスは、単純なランダムウォークがすべてのラマヌジャングラフ上でカットオフ現象を示すことを証明しました。^[16]これは、ランダムウォークが全変動ノルムで完全に混合されていない状態から完全に混合された状態への相転移を起こすことを意味します。この結果は、グラフが単なるエクスパンダーではなくラマヌジャングラフであることに強く依存しています。優れたエクスパンダーの中には、カットオフを示さないものが知られています。^[17]
• ピザーのラマヌジャングラフは、ポスト量子 楕円曲線暗号の基礎として提案されている。^[18]
• ラマヌジャン グラフは、優れたエラー訂正コードであるエクスパンダー コードの構築に使用できます。

• エキスパンダーグラフ
• アロン・ボッパナ行き
• 拡張混合補題
• スペクトルグラフ理論

• ジュリアナ・ダビドフ、ピーター・サーナック、アラン・ヴァレット（2003年）。初等数論、群論、ラマヌジャングラフ。LMS学生用テキスト。第55巻。ケンブリッジ大学出版局。ISBN 0-521-53143-8. OCLC  50253269.
• 砂田俊一 (1986)。「幾何学におけるL関数とその応用」。塩浜勝弘、酒井隆、砂田俊一 (編)。リーマン多様体の曲率と位相: 1985 年 8 月 26 日から 31 日まで堅田で開催された第 17 回国際谷口シンポジウムの議事録。数学の講義ノート。第 1201 巻。ベルリン:シュプリンガー。pp. 266–284。doi :10.1007/ BFb0075662。ISBN 978-3-540-16770-9MR  0859591 。

• M. ラム・マーティによる調査論文
• アレクサンダー・ルボツキーによる調査論文
• Hoory、Linial、Wigdersonによる調査論文