ジグザグ製品

グラフ理論において、で表される正則グラフのジグザグ積は、大きなグラフ ( ) と小さなグラフ ( ) を受け取り、大きなグラフのサイズをほぼ継承し、小さなグラフの次数を継承するグラフを生成する二項演算です。ジグザグ積の重要な特性は、 が適切な拡張子である場合、結果として得られるグラフの拡張は の拡張よりもわずかに劣るだけであるということです。 ${\displaystyle G,H}$${\displaystyle G\circ H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$

大まかに言えば、ジグザグ積はの各頂点をのコピー (クラウド) に置き換え、クラウド内で小さなステップ (ジグ) を移動して頂点を接続し、続いて 2 つのクラウド間で大きなステップ (ザグ) を実行し、最後に宛先クラウド内で別の小さなステップを実行します。 ${\displaystyle G\circ H}$${\displaystyle G}$${\displaystyle H}$

ジグザグ積は、Reingold、Vadhan、Wigderson (2000) によって導入されました。ジグザグ積が最初に導入されたとき、定数次数の拡張子と抽出子の明示的な構築に使用されました。その後、ジグザグ積は、対称ログ空間とログ空間が等しいことを証明するために計算複雑性理論で使用されました(Reingold 2008)。

を 上の -正則グラフで回転写像を持ち、を上の-正則グラフで回転写像を持つとします。ジグザグ積は、上の回転写像が次のようになる-正則グラフとして定義されます。 ${\displaystyle G}$${\displaystyle D}$${\displaystyle [N]}$ ${\displaystyle \mathrm {Rot} _{G}}$${\displaystyle H}$${\displaystyle d}$${\displaystyle [D]}$${\displaystyle \mathrm {Rot} _{H}}$${\displaystyle G\circ H}$${\displaystyle d^{2}}$${\displaystyle [N]\times [D]}$${\displaystyle \mathrm {Rot} _{G\circ H}}$
${\displaystyle \mathrm {Rot} _{G\circ H}((v,a),(i,j))}$

1. させて。${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$
2. させて。${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$
3. させて。${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$
4. 出力.${\displaystyle ((w,b),(j',i'))}$

ジグザグ積の定義から、グラフが-正則な新しいグラフに変換されることは明らかです。したがって、が よりも大幅に大きい場合、ジグザグ積は の次数を減らします。大まかに言えば、 の各頂点をの積のサイズのクラウドに拡大することにより、 は実際に元の各頂点の辺を、それを置き換えるクラウドの頂点間で分割します。 ${\displaystyle G}$${\displaystyle d^{2}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$

グラフの展開はスペクトルギャップによって測定できますが、ジグザグ積の重要な特性はスペクトルギャップが保存されることです。つまり、 が「十分に良い」エクスパンダー（大きなスペクトルギャップを持つ）である場合、ジグザグ積の展開は の元の展開に近くなります。 ${\displaystyle H}$${\displaystyle G}$

正式には、 -グラフを、（関連するランダムウォークの）2番目に大きい固有値の絶対値が最大 である、頂点上の任意の -正則グラフとして定義します。 ${\displaystyle (N,D,\lambda )}$${\displaystyle D}$${\displaystyle N}$${\displaystyle \lambda}$

を-グラフ、を-グラフとすると、 は-グラフになります(ただし ) 。 ${\displaystyle G_{1}}$${\displaystyle (N_{1},D_{1},\lambda _{1})}$${\displaystyle G_{2}}$${\displaystyle (D_{1},D_{2},\lambda _{2})}$${\displaystyle G_{1}\circ G_{2}}$${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$

ジグザグ積は、の各接続コンポーネントに対して個別に演算されます。 ${\displaystyle G\circ H}$${\displaystyle G}$

正式に言うと、上の -正則グラフと上の-正則グラフの 2 つのグラフが与えられ、が の連結要素である場合、 はによって誘導されるのサブグラフです（つまり、の頂点間ののすべての辺を含む 上のグラフ）。 ${\displaystyle G}$${\displaystyle D}$${\displaystyle [N]}$${\displaystyle H}$${\displaystyle d}$${\displaystyle [D]}$${\displaystyle S\subseteq [N]}$${\displaystyle G}$${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D}}$${\displaystyle G|_{S}}$${\displaystyle G}$${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

2002 年に、Omer Reingold、Salil Vadhan、Avi Wigderson は、定数次数エクスパンダー グラフの単純で明示的な組み合わせ構築法を提示しました。構築は反復的で、基本的な構成要素として定数サイズの単一のエクスパンダーが必要です。各反復では、ジグザグ積を使用して、次数と拡張は変更せずにサイズが増加する別のグラフを生成します。このプロセスが継続され、任意の大きさのエクスパンダーが生成されます。

前述のジグザグ積の特性から、大きなグラフと小さなグラフの積は、大きなグラフと同様のサイズと小さなグラフと同様の次数を継承し、両方の拡張特性を保持するため、悪影響なしに拡張器のサイズを大きくできることがわかります。

2005 年に、Omer Reingold は、対数空間のみを使用して、無向グラフ内の 2 つの指定された頂点間にパスがあるかどうかをテストする問題である無向st 連結性問題を解決するアルゴリズムを発表しました。このアルゴリズムは、ジグザグ積に大きく依存しています。

大まかに言えば、対数空間における無向 st 接続問題を解決するには、累乗とジグザグ積の組み合わせを使用して、入力グラフを対数直径を持つ一定次数の正規グラフに変換します。累乗積は次数の増加を犠牲にして拡張を増加させ (したがって直径を減少させます)、ジグザグ積は拡張を維持しながら次数を減らすために使用されます。

• グラフ操作

• Reingold, O. ; Vadhan, S. ; Wigderson, A. (2000)、「エントロピー波、ジグザググラフ積、および新しい定数次数拡張器と抽出器」、Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS)、pp. 3–13、arXiv : math/0406038、doi :10.1109/SFCS.2000.892006。
• Reingold, O (2008)、「対数空間における無向接続性」、Journal of the ACM、55 (4): 記事 17、24 ページ、doi :10.1145/1391289.1391291。
• Reingold, O. ; Trevisan, L. ; Vadhan, S. (2006)、「正規有向グラフ上の擬似ランダムウォークと RL 対 L 問題」、Proc. 38th ACM Symposium on Theory of Computing (STOC)、pp. 457–466、doi :10.1145/1132516.1132583。