エキスパンダーグラフ

n個の頂点を持つグラフGの辺拡張（等周数またはチーガー定数とも呼ばれる）h ( G )は次のように定義される。

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

どこ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\$ :\ u\in S,v\notin S\},}

これは、∂ S = E ( S , S )と書くこともできます。 ここで、 S  := V ( G ) \ S はSの補集合であり、

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\$ :\ u\in A,v\in B\}}

頂点のサブセットA、B ⊆ V ( G )間のエッジ。

この式では、最小値は、頂点数が最大でn ⁄ 2個の空でない集合S全体にわたって求められ、∂ SはSのエッジ境界、つまりS内にちょうど 1 つの端点を持つエッジの集合です。^{[ 2 ]}

直感的に、

${\displaystyle \min {|\partial S|}=\min |E({S},{\overline {S}})|}$

は、グラフを 2 つに分割するために切断する必要のある最小のエッジ数です。エッジ拡張は、2 つの部分で最小の頂点数で割ることによってこの概念を正規化します。正規化によって値がどのように大きく変化するかを確認するために、次の例を考えてみましょう。頂点数nが同じ 2 つの完全グラフを用意し、2 つのグラフの頂点を 1 対 1 で接続して、2 つのグラフ間にn 個のエッジを追加します。最小切断数はnですが、エッジ拡張は 1 になります。

min | ∂ S |では、最適化は0 ≤ | S | ≤ n ⁄ 2または任意の空でない部分集合のどちらに対して も同等に実行できることに注意してください。${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$h ( G )については、 | S |による正規化のため、同じことは当てはまりません。すべての空でない部分集合に対する最適化を用いてh ( G )を記述したい場合は、次のように書き換えることができます。

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {|E({S},{\overline {S}})|}{\min\{|S|,|{\overline {S}}|\}}}.}$

グラフGの頂点等周数h _out ( G ) (頂点拡張または拡大とも呼ばれる)は次のように定義される。

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

ここで、∂ _out ( S )はSの外側境界、すなわち、 S内に少なくとも 1 つの隣接頂点を持つV ( G ) \ S内の頂点の集合です。^{[ 3 ]}この定義の変形 (一意隣接拡張と呼ばれる)では、 ∂ _out ( S )は、 S内にちょうど1 つの隣接頂点を持つV内の頂点の集合に置き換えられます。^{[ 4 ]}

グラフGの( G )_における頂点等周数hは次のように定義される。

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

どこ${\displaystyle \partial _{\text{in}}(S)}$はSの内部境界、すなわち、 V ( G ) \ Sに少なくとも 1 つの隣接点を持つS内の頂点の集合である。^{[ 3 ]}

Gがd正則である場合、Gの隣接行列A = A ( G )の固有値に基づいて、線形代数的な拡張の定義が可能であり、ここでA _ijは頂点iとjの間のエッジの数である。^{[ 5 ]} A は対称であるため、スペクトル定理は、 Aがn 個の実数値固有値λ ₁ ≥ λ ₂ ≥ … ≥ λ _nを持つことを意味する。これらの固有値はすべて[− d , d ]に含まれることが知られており、より具体的には、 λ _n = − dとなるのはG が二部グラフである場合のみであることが知られている。

より厳密には、n頂点、d正則グラフを次のように表します。

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

( n , d , λ )グラフとして。i ≠ 1のλ _i上の( n , d , λ )グラフによって与えられる境界は、エキスパンダー混合補題を含む多くの文脈で有用です。

スペクトル展開は、上記のように両側から行うことができ、${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$あるいは、一方的なものになることもあります。${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$後者は二部グラフにも当てはまる弱い概念であり、アロン・チャン補題など多くの応用において依然として有用である。^{[ 6 ]}

Gは正規分布であるため、一様分布${\displaystyle u\in \mathbb {R} ^{n}}$u _i = 1 ⁄ n ( i = 1, …, nすべて) はGの定常分布です。つまり、Au = duであり、uはAの固有値λ ₁ = dを持つ固有ベクトルです。ここでdはGの頂点の次数です。Gのスペクトルギャップはd − λ ₂と定義され、グラフGのスペクトル拡張を測定します。^{[ 7 ]}

設定すると

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

これはuに直交する固有ベクトルに対応する最大の固有値であるため、レイリー商を用いて同等に定義することができる。

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

どこ

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

はベクトルの2ノルムです${\displaystyle v\in \mathbb {R} ^{n}}$。

これらの定義の正規化バージョンも広く使用されており、いくつかの結果を述べるのに便利です。ここでは、グラフGのマルコフ遷移行列である行列⁠ 1 / d ⁠ Aを考えます。その固有値は −1 から 1 の間です。必ずしも正則グラフではない場合、グラフのスペクトルは、ラプラシアン行列の固有値を使用して同様に定義できます。有向グラフの場合、隣接行列Aの特異値を考えます。これは、対称行列A ^T Aの固有値の根に等しくなります。

家族${\displaystyle (G_{i})_{i\in \mathbb {N} }}$の${\displaystyle d}$- 増大する正則グラフは、以下の条件を満たす場合、エクスパンダーファミリーです。${\displaystyle h(G_{i})}$ゼロから離れた範囲に収束する。^{[ 8 ]}

Gがd正則、つまり各頂点の次数がdである場合、等周定数h ( G )とGの隣接演算子のスペクトルのギャップd − λ ₂の間には関係があります。標準的なスペクトルグラフ理論によれば、 d正則グラフの隣接演算子の自明な固有値はλ ₁ = dであり、最初の非自明な固有値はλ ₂です。Gが連結である場合、λ ₂ < dとなります。Dodziuk ^{[ 9 ]}および独立にAlonとMilman ^{[ 10 ]}による不等式は^{[ 11 ]}を示しています。

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

実際、下限はタイトです。下限は、h ( G ) = 1、d – λ2 = 2となるハイパーキューブQn_{の極限で達成されます。上限は、} h ( Cn ) = 4/ n = Θ(1/ _n ) 、 d – λ2 = _{2 – 2cos} (2)となるサイクルで（漸近的に）達成されます。${\displaystyle \pi }$/ n ) ≈ (2${\displaystyle \pi }$/ n ) ² = Θ(1/ n ² )。^{[ 1 ]}より良い境界は^{[ 12 ]}で次のように与えられています。

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

これらの不等式はマルコフ連鎖のチーガー不等式と密接に関連しており、リーマン幾何学におけるチーガーの不等式の離散版と見なすことができる。

頂点等周数とスペクトルギャップの間の同様の関係も研究されている: ^{[ 13 ]}

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

漸近的に言えば、量h ² ⁄ d、h _out、およびh _in ²はすべてスペクトルギャップO ( d – λ ₂ )によって上から抑えられます。

ケーリーグラフに基づく代数的構成は、様々な変形のエキスパンダーグラフについて知られています。以下の構成はマルグリスによるもので、ガバーとガリルによって解析されています。^{[ 16 ]}任意の自然数nに対して、頂点集合を持つグラフG _{n を考えます。}${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$、 どこ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$: すべての頂点について${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$、その8つの隣接頂点は

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

すると、以下のことが成り立つ。

定理。すべてのnに対して、グラフG _{n は}2 番目に大きい固有値を持つ。${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$。

アロンとボッパナの定理によれば、十分に大きなd正則グラフはすべて以下を満たす。${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$ここで、λ ₂は絶対値で 2 番目に大きい固有値です。^{[ 17 ]}直接的な結果として、任意の固定されたdに対して、${\displaystyle \lambda <2{\sqrt {d-1}}}$有限個の( n , d , λ ) -グラフしか存在しない。ラマヌジャングラフは、この境界がタイトで、 ^{[ 18 ]}を満たすd -正則グラフである。

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

したがって、ラマヌジャングラフは漸近的に最小のλ2値を持つ。このため_、ラマヌジャングラフは優れたスペクトル拡張器となる。

Lubotzky、Phillips、Sarnak（1988）、Margulis（1988）、Morgenstern（1994）は、ラマヌジャングラフを明示的に構築する方法を示している。^{[ 19 ]}

1985年、アロンは、n個の頂点を持つほとんどのd正則グラフは、 nが十分に大きい場合、ほぼラマヌジャンであると推測した。^{[ 20 ]}つまり、ε > 0の場合、それらは次の条件を満たす。

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$。

2003年、ジョエル・フリードマンは、ランダムなd正則グラフが${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$確率1 – O ( n ^-τ )ですべてのε > 0に対して、ここで^{[ 21 ] [ 22 ]}

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

プーダーは、やや弱い結果のより簡単な証明を与えた。^{[ 23 ] [ 24 ] [ 25 ]}

Marcus、Spielman、Srivastavaは[ ^{26 ] [ 27 ]リフト}に基づく二部ラマヌジャングラフの構成法を示した。

2024年にJiaoyang Huang、Theo McKenzie、Horng-Tzer Yauによるプレプリントで、

${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$。

固有値のうち、アロン・ボッパナ境界に達する割合が約69%であることから、エッジ普遍性が成り立つことが証明され、すなわち、ガウス直交アンサンブルに関連付けられたトレーシー・ウィドム分布に従うことが示された^{[ 28 ] [ 29 ]。}

Reingold、Vadhan、およびWigdersonは2000年にジグザグ積を導入しました。^{[ 30 ]} 大まかに言えば、2つのエクスパンダーグラフのジグザグ積は、わずかに劣る拡張のグラフを生成します。したがって、ジグザグ積はエクスパンダーグラフの族を構築するためにも使用できます。G_が(n、d、λ1 )グラフで、 Hが( m、d、λ2)グラフである場合、ジグザグ_積G◦Hは、φが_次の特性を持つ⁽ nm 、 d2 、 φ ( λ1 、 λ2 ) ₎グラフです。

1. λ ₁ < 1かつλ ₂ < 1の場合、φ ( λ ₁ , λ ₂ ) < 1 になります。
2. φ ( λ ₁ , λ ₂ ) ≤ λ ₁ + λ ₂。

具体的には、^{[ 30 ]}

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

性質（1）は、2つのエキスパンダーグラフのジグザグ積もエキスパンダーグラフであることを意味するので、ジグザグ積を帰納的に使用してエキスパンダーグラフの族を作成できます。

直感的に、ジグザグ積の構成は次のように考えることができます。G の各頂点は、 m個の頂点の「雲」に拡大され、それぞれの頂点は、その頂点に接続された異なるエッジに関連付けられます。各頂点は、( v , k )とラベル付けされます。ここで、v はGの元の頂点を指し、k はvのk番目のエッジを指します。2 つの頂点( v , k )と( w , ℓ )は、次の移動シーケンスによって( v , k )から( w , ℓ )に到達できる場合に、接続されます。

1. ジグ- Hのエッジを使用して( v , k )から( v , k' )に移動します。
2. Gのエッジk'を使用して雲を飛び越え、 ( w , ℓ ′ )に到達します。
3. ザグ– Hのエッジを使用して( w , ℓ ′ )から( w , ℓ )へ移動する。^{[ 30 ]}

グラフの r リフトは、各頂点を r 個の頂点に置き換え、各エッジを対応する集合間のマッチングに置き換えることによって形成されます。${\displaystyle r}$頂点。持ち上げられたグラフは元のグラフの固有値を継承し、いくつかの追加の固有値を持つ。BiluとLinial ^{[ 31 ] [ 32 ]}は、すべてのd正則グラフには、追加の固有値が最大で2である2リフトが存在することを示した。${\displaystyle O({\sqrt {d\log ^{3}d}})}$大きさにおいて。また、開始グラフが十分に良いエキスパンダーであれば、良い2リフトを多項式時間で見つけることができ、それによってすべてのdに対してd正則エキスパンダーの効率的な構成が得られることも示しました。

ビルとリニアルは、境界が${\displaystyle O({\sqrt {d\log ^{3}d}})}$改善できる${\displaystyle 2{\sqrt {d-1}}}$これは、 Alon–Boppana の限界により最適となる。この予想は、 Marcus、Spielman、Srivastava ^{[ 26 ] [ 27 ]}によって二部グラフの設定で証明され、彼らは多項式の交錯法を使用した。その結果、彼らは二部グラフ Ramanujan グラフの別の構成を得た。元の非構成的な証明は、Michael B. Cohen によってアルゴリズムに変換された。^{[ 33 ]}その後、この方法は Hall、Puder、Sawin によってr-リフトに一般化された。^{[ 34 ]}

確率論的議論によって、優れた拡張特性を持つグラフの存在を示す結果が数多くあります。実際、エクスパンダーの存在は、Pinsker ^{[ 35 ]}によって最初に証明されました。彼は、ランダムに選択されたn個の頂点を持つd個の正則二部グラフに対して、 すべての頂点部分集合| S | ≤ c _d nに対して、高い確率で| N ( S ) | ≥ ( d – 2) | S |となることを示しました。ここで、c _{d は}dに依存する定数で、O ( d ^-4 )です。Alon と Roichman ^{[ 36 ]}は、任意の1 > ε > 0に対して、次のことが成り立つc ( ε ) > 0が存在することを示しました。位数nの群Gに対して、 Gからランダムに選択されたc ( ε ) log ₂ n個の要素を持つG上のケイリー グラフを考えます。すると、 nが無限大に近づく極限では、結果として得られるグラフはほぼ確実にεエクスパンダーになります。

2021年、アレクサンダーはMCMCアルゴリズムを修正し、固定された頂点サイズと規則性の次数を持つラマヌジャングラフを生成するランダムな構成を探しました。^{[ 37 ]}結果は、頂点サイズと次数の組み合わせが最大2000頂点までであれば、ラマヌジャングラフが存在することを示しています。

2024年、アロンはあらゆる頂点サイズと次数の組み合わせについて、ほぼラマヌジャングラフの明示的な構成法を発表した。

エクスパンダー混合補題は、( n , d , λ )グラフにおいて、頂点の任意の 2 つの部分集合S、T ⊆ Vに対して、 SとTの間のエッジの数は、ランダムd正則グラフで期待される数とほぼ一致すると述べています。λが小さいほど、近似精度は向上します。ランダムd正則グラフ、およびエッジ確率d ⁄ n のErdős–Rényi ランダムグラフでは、 SとTの間にd ⁄ n • | S | • | T |個のエッジが存在すると予想されます。

より厳密には、E ( S , T )をSとTの間のエッジの数とします。2 つの集合が互いに素でない場合、それらの交差部分のエッジは 2 回カウントされます。つまり、

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

すると、エキスパンダー混合補題によれば、次の不等式が成り立つ。

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

( n , d , λ )グラフの多くの特性は、以下のものを含め、エクスパンダー混合補題の系である。^{[ 1 ]}

• グラフの独立集合とは、隣接する頂点が存在しない頂点の部分集合のことです。 ( n , d , λ )グラフでは、独立集合のサイズは最大でλn / dです。
• グラフGの彩色数χ ( G )は、隣接する頂点が異なる色を持つために必要な最小の色数です。ホフマンはd ⁄ λ ≤ χ ( G )であることを示しました^{[ 38 ]}一方、アロン、クリヴェレヴィッチ、スダコフは、d < 2 n ⁄ 3 の場合[ 39 ]であることを示し^ました。

${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• グラフの直径は、2 つの頂点間の最大距離であり、2 つの頂点間の距離は、それらの間の最短経路として定義されます。Chung は、( n , d , λ )グラフの直径は最大で^{[ 40 ]であることを示しました。}

${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

チェルノフ限界は、 [−1, 1]の範囲の確率変数から多数の独立したサンプルをサンプリングする場合、高い確率でサンプルの平均が確率変数の期待値に近くなることを示しています。Ajtai 、Komlós 、 Szemerédi (1987)およびGillman (1998)によるエキスパンダーウォークサンプリング補題は、エキスパンダーグラフ上のウォークからサンプリングする場合にもこれが成り立つことを示しています。これは、エキスパンダーウォークに従ってサンプリングする場合、独立にサンプリングする場合よりもはるかに少ない乱数ビットを使用するため、脱ランダム化の理論において特に有用です。

ソートネットワークは、一連の入力を受け取り、一連の並列ステップを実行して入力をソートします。並列ステップは、任意の数の互いに素な比較を実行し、比較された入力のペアを交換することから構成されます。ネットワークの深さは、実行される並列ステップの数によって決まります。エキスパンダーグラフは、深さO (log n )を実現するAKSソートネットワークにおいて重要な役割を果たします。これは漸近的にソートネットワークの既知の最良の深さですが、エキスパンダーへの依存により、定数の上限が実用上大きすぎます。

AKSソートネットワークでは、エキスパンダーグラフを使用して、深さが制限されたε-ハーフグラフを構築します。ε-ハーフグラフは、 (1, …, n )の長さnの順列を入力として受け取り、入力を互いに素な2つの集合AとBに分割します。各整数k ≤ n ⁄ 2に対して、 k個の最小入力のうち最大εk個がBに含まれ、 k個の最大入力のうち最大εk個がAに含まれるようにします。集合AとBはε-ハーフグラフです。

Ajtai、Komlós 、 Szemerédi (1983)に従って、深さd εハーフは次のように構築できます。n個の頂点、次数dの二部グラフ拡張器を考えます。部分XとYのサイズは等しく、サイズが最大εn の頂点の任意の部分集合には、少なくとも1 – ε / ε個の隣接点があります。

グラフの頂点は入力を含むレジスタ、辺は2つのレジスタの入力を比較するワイヤと考えることができます。最初に、入力の半分をXに、残りの半分をYに任意に配置し、辺をd個の完全一致に分解します。目標は、Xに入力の小さい方の半分が、Yに入力の大きい方の半分がほぼ含まれるようにすることです。これを実現するには、各一致を順次処理し、その一致の辺によってペアになったレジスタを比較して、順序が間違っている入力を修正します。具体的には、一致の各辺について、大きい方の入力がXのレジスタにあり、小さい方の入力がYのレジスタにある場合は、2つの入力を交換して、小さい方がXに、大きい方がYにあるようにします。このプロセスはd個の並列ステップから構成されていることは明らかです。

dラウンドすべて後、 A をXのレジスタ内の入力の集合、B をYのレジスタ内の入力の集合として、 ε半減を取得します。これを確認するには、 XのレジスタuとYのレジスタvがエッジuvで接続されている場合、このエッジとのマッチングが処理された後、 uの入力はvの入力よりも小さくなることに注意してください。さらに、この性質はプロセスの残りの間ずっと真であり続けます。ここで、k ≤ n ⁄ 2に対して、入力(1, …, k )のうちεk を超えるものがBにあると仮定します。すると、グラフの拡張特性により、 Yのこれらの入力のレジスタは、Xの少なくとも 1 – ε / ε k 個のレジスタに接続されます。合計すると、 kを超えるレジスタが構成されるため、 XのレジスタA がYのレジスタBに接続され、 Aの最終入力が(1, …, k )に含まれず、 Bの最終入力が(1, …, k )に含まれるようなレジスタ A が存在する必要があります。しかし、これは前述の性質に違反するため、出力セット AとBはε-半減でなければならない。