アロン-ボッパナ行き

スペクトルグラフ理論において、アロン・ボッパナ境界は、 -正則グラフ^[1]、つまりすべての頂点が次数を持つグラフの隣接行列の2番目に大きい固有値の下限を提供します。2番目に大きい固有値に関心があるのは、最大の固有値が-正則性によるものであることが保証されており、すべて1のベクトルが関連する固有ベクトルであるためです。この境界を満たすのに近いグラフはラマヌジャングラフであり、これは可能な限り最高のエクスパンダーグラフの例です。 ${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$

発見者はノガ・アロンとラヴィ・ボッパナです。

を直径 の頂点を持つ -正則グラフとし、をその隣接行列とする。をその固有値とする。すると ${\displaystyle G}$${\displaystyle d}$${\displaystyle n}$${\displaystyle m}$${\displaystyle A}$${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$

${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.}$

上記の記述は、 Noga Alonによって証明されたオリジナルの記述です。証明を容易にしたり直感性を高めたりするために、やや弱い変形もいくつか存在します。これらのうち 2 つを以下の証明に示します。

この数の直感は無限正則木を考えることから得られる。^[2]このグラフは正則グラフの普遍被覆であり、スペクトル半径は${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle d}$${\displaystyle d}$ ${\displaystyle 2{\sqrt {d-1}}.}$

アロン・ボッパナ境界を本質的に満たすグラフはラマヌジャングラフと呼ばれる。より正確には、ラマヌジャングラフは次のような -正則グラフである。${\displaystyle d}$${\displaystyle |\lambda _{2}|,|\lambda _{n}|\leq 2{\sqrt {d-1}}.}$

フリードマンの定理^[3]によれば、任意の および に対して、かつ十分に大きい に対して、頂点上のランダム-正則グラフは高い確率で を満たす。これは、ランダム-頂点 -正則グラフが典型的には「ほぼラマヌジャン」である ことを意味する。${\displaystyle d}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle d}$${\displaystyle G}$${\displaystyle n}$${\displaystyle \max\{|\lambda _{2}|,|\lambda _{n}|\}}2{\sqrt {d-1}}+\epsilon }$ ${\displaystyle n}$${\displaystyle d}$

ここでは、 2 番目の項の特異性を省略し、単に次のように主張することで、やや弱い主張を証明します。ここで、項は、が無制限に増加し、が固定されているときの漸近的な動作を指します。 ${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1).}$${\displaystyle o(1)}$${\displaystyle n}$${\displaystyle d}$

頂点集合を とすると、最小最大定理により、となる非ゼロベクトルを構築すれば十分であり、${\displaystyle V.}$${\displaystyle z\in \mathbb {R} ^{|V|}}$${\displaystyle z^{\text{T}}\mathbf {1} =0}$${\displaystyle {\frac {z^{\text{T}}Az}{z^{\text{T}}z}}\geq 2{\sqrt {d-1}}-o(1).}$

値を選ぶグラフの各頂点に対して、次のようにベクトルを定義する。各成分はグラフの頂点によってインデックスされる。各 に対して、と の間の距離が である場合、の -成分はであり、である場合、このようなベクトルはどれもを満たす と主張する。${\displaystyle r\in \mathbb {N} .}$${\displaystyle V,}$${\displaystyle f(v)\in \mathbb {R} ^{|V|}}$${\displaystyle u}$${\displaystyle u,}$${\displaystyle u}$${\displaystyle v}$${\displaystyle k,}$${\displaystyle u}$${\displaystyle f(v)}$${\displaystyle f(v)_{u}=w_{k}=(d-1)^{-k/2}}$${\displaystyle k\leq r-1}$${\displaystyle 0}$${\displaystyle k\geq r.}$${\displaystyle x=f(v)}$

${\displaystyle {\frac {x^{\text{T}}Ax}{x^{\text{T}}x}}\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right).}$

これを証明するには、からちょうど距離を持つすべての頂点の集合をとします。まず、 ${\displaystyle V_{k}}$${\displaystyle k}$${\displaystyle v.}$

${\displaystyle x^{\text{T}}x=\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.}$

第二に、

${\displaystyle x^{\text{T}}Ax=\sum _{u\in V}x_{u}\sum _{u'\in N(u)}x_{u'}\geq \sum _{k=0}^{r-1}|V_{k}|w_{k}\left[w_{k-1}+(d-1)w_{k+1}\right]-(d-1)|V_{r-1}|w_{r-1}w_{r},}$

ここで、右辺の最後の項は、最初の式で項が多すぎる可能性から生じている。したがって、上記は次を意味する。

${\displaystyle x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}-{\frac {1}{2}}|V_{r-1}|w_{r-1}^{2}\right),}$

これを、任意の利回り に対して${\displaystyle |V_{k+1}|\leq (d-1)|V_{k}|}$${\displaystyle k,}$

${\displaystyle x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.}$

上記の結果を組み合わせると、目的の不等式が証明されます。

便宜上、頂点の -球を、から最大で までの距離を持つ頂点の集合として定義します。頂点に対応するのエントリがゼロでないのは、が の -球内にある場合のみであることに注意してください。${\displaystyle (r-1)}$${\displaystyle v}$${\displaystyle r-1}$${\displaystyle v.}$${\displaystyle f(v)}$${\displaystyle u}$${\displaystyle u}$${\displaystyle (r-1)}$${\displaystyle x.}$

与えられた頂点からの距離内にある頂点の数は最大である。したがって、少なくとも距離にある頂点が存在する場合、${\displaystyle k}$${\displaystyle 1+d+d(d-1)+d(d-1)^{2}+\cdots +d(d-1)^{k-1}=d^{k}+1.}$${\displaystyle n\geq d^{2r-1}+2,}$${\displaystyle u,v}$${\displaystyle 2r.}$

とととの両方にある頂点は存在しないので、となる。の -球面にある頂点はの-球面にある頂点に隣接できないので、となることも真である。${\displaystyle x=f(v)}$${\displaystyle y=f(u).}$${\displaystyle x^{\text{T}}y=0,}$${\displaystyle (r-1)}$${\displaystyle x}$${\displaystyle y.}$${\displaystyle x^{\text{T}}Ay=0,}$${\displaystyle (r-1)}$${\displaystyle x}$${\displaystyle (r-1)}$${\displaystyle y.}$

さて、を満たす定数が存在する。すると、${\displaystyle c}$${\displaystyle z=x-cy}$${\displaystyle z^{\text{T}}\mathbf {1} =0.}$${\displaystyle x^{\text{T}}y=x^{\text{T}}Ay=0,}$

${\displaystyle z^{\text{T}}Az=x^{\text{T}}Ax+c^{2}y^{\text{T}}Ay\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)(x^{\text{T}}x+c^{2}y^{\text{T}}y)=2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)z^{\text{T}}z.}$

最後に、 を の関数として準対数的に増加させることで、 を無制限に増加させることを保証すると（これはを の関数として準対数的に増加させることで実現できます）、の誤差項は${\displaystyle r}$${\displaystyle n\geq d^{2r-1}+2}$${\displaystyle r}$${\displaystyle n}$${\displaystyle o(1)}$${\displaystyle n.}$

この証明では、若干修正された結果を示しますが、数字の出所についてより直感的に理解できます。${\displaystyle 2{\sqrt {d-1}}.}$${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1),}$${\displaystyle \lambda =\max(|\lambda _{2}|,|\lambda _{n}|)\geq 2{\sqrt {d-1}}-o(1).}$

まず、ある値を選びます。長さの閉じた歩道の数は ${\displaystyle k\in \mathbb {N} .}$${\displaystyle 2k}$

${\displaystyle \operatorname {tr} A^{2k}=\sum _{i=1}^{n}\lambda _{i}^{2k}\leq d^{2k}+n\lambda ^{2k}.}$

しかし、 -正則グラフ内の固定された頂点から始まる長さ の閉じたウォークの数は、無限 -正則木内のそのようなウォークの数以上であることも事実です。これは、無限 -正則木を使用してグラフをカバーできるためです。カタラン数の定義により、この数は少なくとも であり、 はカタラン数です。 ${\displaystyle 2k}$${\displaystyle v}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle C_{k}(d-1)^{k},}$${\displaystyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}}$${\displaystyle k^{\text{th}}}$

すると、

${\displaystyle \operatorname {tr} A^{2k}\geq n{\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}}$

${\displaystyle \implies \lambda ^{2k}\geq {\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}-{\frac {d^{2k}}{n}}.}$

際限なく成長させ、際限なく成長させるが、収穫量は対数以下になる${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle \lambda \geq 2{\sqrt {d-1}}-o(1).}$