ラマヌジャングラフ

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

定義

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

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

構成

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

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

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

関連項目

脚注または引用文献

  1. ^ Murty.
  2. ^ Lubotzky, Phillips & Sarnak (1988).
  3. ^ Moshe Morgenstern (1994). “Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q”. Journal of Combinatorial Theory, Series B 62: 44–62. doi:10.1006/jctb.1994.1054. 

雑誌

  • Lubotzky, Alexander; Phillips, Ralph; Sarnak, Peter (1988). “Ramanujan graphs”. Combinatorica 8 (3): 261-277. doi:10.1007/BF02126799. 
  • Murty, M. Ram (Jan. 8, 2003). “Ramanujan Graphs”. J. Ramanujan Math. Soc. 18 (1): 1-20. http://www.mast.queensu.ca/~murty/ramanujan.pdf. 

参考文献

  • Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003). Elementary number theory, group theory and Ramanujan graphs. LMS students texts. 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269 
  • Toshikazu, Sunada (1985). L-functions in geometry and some applications. Lecture Note in Mathematics. 1201. pp. 266-284. doi:10.1007/BFb0075662. ISBN 978-3-540-16770-9 
  • 平松, 豊一、知念, 宏司『有限数学入門:有限上半平面とラマヌジャングラフ』（初版）牧野書店、東京都北区西ヶ原、2003年8月10日。ISBN 4-434-03407-3。