「ラマヌジャングラフ」の版間の差分

削除された内容追加された内容

インライン

2020年2月12日 (水) 07:01時点における版

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

定義

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

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

構成

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

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

任意の $d>3$ について、幾つかの無限な（2部（英: bipartite）でない） $d$ -正則なラマヌジャングラフが存在するかどうかは、未解決である。とりわけ、 $d=7$ については解かれていない、最小の $d=1$ の場合では素数の冪（べき）ではなくしたがってモルゲンシュタインの構成は応用できない。

雑誌

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.

参考文献

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。

[FOOTNOTEMurty-1] Murty.

[FOOTNOTELubotzkyPhillipsSarnak1988-2] Lubotzky, Phillips & Sarnak (1988).

[1]

[2]

@@ 3行目: / 3行目: @@
 == 定義 ==
-<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> の{{日本語版にない記事リンク |スペクトル |en |spectrum}}）とする。<math>G</math>はつながった <math>d</math> -正則グラフなので、それの固有値は、 <math>d = \lambda_1 > \lambda_2</math> <math>\geq \cdots \geq \lambda_n \geq - d</math> を満たす。
+<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> の{{日本語版にない記事リンク |スペクトル |en |spectrum}}）とする。<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> である。
+任意の<math>d > 3</math> について、幾つかの無限な（[[2部グラフ|2部]]（{{lang-en-short|bipartite}}）でない）<math>d</math> -正則なラマヌジャングラフが存在するかどうかは、未解決である。とりわけ、<math>d = 7</math> については解かれていない、最小の<math>d = 1</math> の場合では素数の冪（べき）ではなくしたがってモルゲンシュタインの構成は応用できない。
 == 関連項目 ==
@@ 17行目: / 24行目: @@
 {{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}}