ラマヌジャングラフのソースを表示

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

== 定義 ==

<math>G</math> を[[連結グラフ|''つながった'']]（{{lang-en-short|connected}}）<math>n</math> 個の頂点をもった <math>d</math> -正則グラフとする、そして <math>\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n</math> を <math>G</math> の[[接続行列]]の[[固有値]]（もしくは <math>G</math> の[[スペクトル]]）とする。<math>G</math>はつながった <math>d</math> -正則グラフなので、それの固有値は、 <math>d = \lambda_1 > \lambda_2</math> <math>\geq \cdots \geq \lambda_n \geq - d</math> を満たす。

<math>\lambda(G) = \max_{i \neq 1} | \lambda_i | = \max( | \lambda_2 |, | \lambda_n | )</math> と定義する。もし <math>\lambda(G) \leq 2 \sqrt{ d - 1 }</math> を満たすならば、 <math>d</math> -正則グラフは ''ラマヌジャングラフ'' である。

== 構成 ==

固定した<math>d</math> ごとにたいする<math>d</math> -正則なラマヌジャングラフの構成について、数学者たちはしばしば興味をいだく。このようなラマヌジャングラフの''無限な族''（{{lang-en-short|infinite family}}）の現在の構成は、しばしば代数的である。
* <math>p</math> が[[素数]]で、<math>4</math> を法として<math>1</math> と[[合同式|合同]]な場合に、[[:en:Alexander Lubotzky |ルボツキー]]、[[:en:Ralph S. Phillips |フィリップス]]、[[ピーター・サルナック|サルナック]]{{sfnp|Lubotzky|Phillips|Sarnak|1988}}は、<math>( p + 1 )</math> -正則ラマヌジャングラフの或る無限な族をどうやって構成するかを示した。ラマヌジャングラフの呼称を由来させる、[[ラマヌジャン・ピーターソン予想]]を、彼らの証明は用いる。ラマヌジャングラフであることに加えて、彼らの構成は幾つかの性質を満たす、たとえば、<math>n</math> をその辺の数として、それらの[[内周 (グラフ理論)|内周]]は<math>\Omega ( \log_{ p } ( n ) )</math> である。
* モルゲンシュテルン<ref name="m94">{{cite journal|author=Moshe Morgenstern|year=1994|title=Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q|journal=Journal of Combinatorial Theory, Series B|volume=62|pages=44–62|doi=10.1006/jctb.1994.1054}}</ref>はルボツキー、フィリップス、サルナックの構成を <math>p</math> が素数の冪の場合に拡張した。

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

== 関連項目 ==

* {{日本語版にない記事リンク |拡張グラフ |en |expander graph}}
* {{日本語版にない記事リンク |拡張混合補題 |en |expander mixing lemma}}
* [[スペクトルグラフ理論]]

== 脚注または引用文献 ==

{{Reflist}}
=== 雑誌 ===
* {{cite journal |last1 =Lubotzky |first1 =Alexander |authorlink =:en:Alexander Lubotzky |last2 =Phillips |first2 =Ralph |authorlink2 =:en:Ralph Phillips |last3 =Sarnak |first3 =Peter |authorlink3 =ピーター・サルナック |year =1988 |title =Ramanujan graphs |journal =[[:en:Combinatorica|Combinatorica]] |volume =8 |issue =3 |pages =261-277 |doi =10.1007/BF02126799 |ref =harv}}
* {{cite journal |last =Murty |first =M. Ram |authorlink =:en:M. Ram Murty |date =Jan. 8, 2003 |title =Ramanujan Graphs |journal =J. Ramanujan Math. Soc.|volume =18 |issue =1 |pages =1-20 |url =http://www.mast.queensu.ca/~murty/ramanujan.pdf |ref =harv}}

== 参考文献 ==
* {{cite book |last1 =Davidoff |first1 =Guiliana |last2 =Sarnak |first2 =Peter |authorlink2 =ピーター・サルナック |last3 =Valette |first3 =Alain |title =Elementary number theory, group theory and Ramanujan graphs |publisher =[[:en:Cambridge University Press|Cambridge University Press]] |series =LMS students texts |volume =55 |year =2003 |isbn =0-521-53143-8 |oclc =50253269}}
* {{cite book |last =Toshikazu |first =Sunada |authorlink =砂田利一 |title =L-functions in geometry and some applications |volume =1201 |year =1985 |pages =266-284 |doi =10.1007/BFb0075662 |series =Lecture Note in Mathematics |isbn =978-3-540-16770-9}}
* {{cite book |和書|author1=平松豊一 |author2=知念宏司 |date =2003-08-10|edition =初版|title =有限数学入門：[[有限上半平面]]とラマヌジャングラフ|publisher =牧野書店|location =東京都北区西ヶ原|isbn =4-434-03407-3}}
* 仁平政一：「ラマヌジャングラフへの招待：群・環・体からラマヌジャングラフへ 」、プレアデス出版、ISBN 978-4-90381496-4 (2019年12月5日). 

{{デフォルトソート:らまぬしやん くらふ}}
[[Category:シュリニヴァーサ・ラマヌジャン]]
[[Category:スペクトル理論]]
[[Category:代数的グラフ理論]]
[[Category:数学に関する記事]]