展開混合補題

拡張混合補題は、ある-正則グラフの辺がグラフ全体に均等に分布していることを直感的に示しています。特に、2つの頂点部分集合と 間の辺の数は、ランダム-正則グラフにおけるそれらの間の辺の期待数、すなわち に常に近くなります。 ${\displaystyle d}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle d}$ ${\displaystyle {\frac {d}{n}}|S||T|}$

d-正規展開グラフ

-グラフを、その隣接行列の固有値の1 つを除いてすべて絶対値が最大であるような頂点上の-正則グラフとして定義します。グラフの -正則性により、その固有値の最大絶対値は であることが保証されます。実際、すべて 1 のベクトルは、固有値 を持つの固有ベクトルであり、隣接行列の固有値は、絶対値において の最大次数を超えることはありません。${\displaystyle (n,d,\lambda )}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle A_{G}}$ ${\displaystyle \lambda .}$ ${\displaystyle d}$ ${\displaystyle d.}$ ${\displaystyle \mathbf {1} }$ ${\displaystyle A_{G}}$ ${\displaystyle d}$ ${\displaystyle G}$

とを固定すると、グラフは一定のスペクトルギャップを持つエクスパンダーグラフの族を形成します。 ${\displaystyle d}$ ${\displaystyle \lambda}$ ${\displaystyle (n,d,\lambda )}$

声明

をグラフとする。任意の2つの部分集合 に対し、をSとTの間の辺の数とする（ SとTの交差に含まれる辺を2回数える）。すると、 ${\displaystyle G=(V,E)}$ ${\displaystyle (n,d,\lambda )}$ ${\displaystyle S,T\subseteq V}$ ${\displaystyle e(S,T)=|\{(x,y)\in S\times T:xy\in E(G)\}|}$

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

より緊密な境界

実際に、

${\displaystyle \left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|(1-|S|/n)(1-|T|/n)}}\,}$

同様の技術を使用する。^{[ 1 ]}

双正則グラフ

双正則グラフでは、次の変化があり、ここで は2番目に大きい固有値である。^{[ 2 ]}${\displaystyle \lambda}$

を二部グラフとし、 のすべての頂点が の頂点に隣接し、 のすべての頂点が の頂点に隣接するものとする。 およびととする。 とする。すると ${\displaystyle G=(L,R,E)}$ ${\displaystyle L}$ ${\displaystyle d_{L}}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle d_{R}}$ ${\displaystyle L}$ ${\displaystyle S\subseteq L,T\subseteq R}$ ${\displaystyle |S|=\alpha |L|}$ ${\displaystyle |T|=\beta |R|}$ ${\displaystyle e(G)=|E(G)|}$

${\displaystyle \left|{\frac {e(S,T)}{e(G)}}-\alpha \beta \right|\leq {\frac {\lambda}{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta (1-\alpha )(1-\beta )}}\leq {\frac {\lambda}{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta }}\,.}$

は の最大固有値であることに注意してください。 ${\displaystyle {\sqrt {d_{L}d_{R}}}}$ ${\displaystyle G}$

証明

最初の声明の証明

を の隣接行列とし、を の固有値とします（は対称なので、これらの固有値は実数です）。対応する固有ベクトル は、すべての要素が1であるベクトルの正規化です。 を定義し、 であることに注意してください。 は対称なので、の固有値に対応するの固有ベクトルを取り、が の直交基底を形成するようにすることができます。 ${\displaystyle A_{G}}$ ${\displaystyle G}$ ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{n}}$ ${\displaystyle A_{G}}$ ${\displaystyle A_{G}}$ ${\displaystyle \lambda _{1}=d}$ ${\displaystyle v_{1}={\frac {1}{\sqrt {n}}}\mathbf {1} }$ ${\displaystyle \lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}}$ ${\displaystyle \max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}=\lambda ^{2}\leq \lambda _{1}^{2}=d^{2}}$ ${\displaystyle A_{G}}$ ${\displaystyle v_{2},\ldots ,v_{n}}$ ${\displaystyle A_{G}}$ ${\displaystyle \lambda _{2},\ldots ,\lambda _{n}}$ ${\displaystyle \{v_{1},\ldots ,v_{n}\}}$ ${\displaystyle \mathbf {R} ^{n}}$

をすべて1とする行列とする。は固有値を持つの固有ベクトルであり、 は互いに垂直であり、 は固有値0を持つ の固有ベクトルであることに注意する。頂点部分集合 について、の場合には座標が1、 の場合には座標が0となる列ベクトルとする。すると、 ${\displaystyle J}$ ${\displaystyle n\times n}$ ${\displaystyle v_{1}}$ ${\displaystyle J}$ ${\displaystyle n}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{1}=\mathbf {1} }$ ${\displaystyle J}$ ${\displaystyle U\subseteq V}$ ${\displaystyle 1_{U}}$ ${\displaystyle v^{\text{th}}}$ ${\displaystyle v\in U}$

${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|=\left|1_{S}^{\operatorname {T} }\left(A_{G}-{\frac {d}{n}}J\right)1_{T}\right|}$ 。

とする。と は固有ベクトルを共有するので、 の固有値はとなる。コーシー・シュワルツの不等式より、 となる。さらに、は自己随伴なので、 と書くことができる。 ${\displaystyle M=A_{G}-{\frac {d}{n}}J}$ ${\displaystyle A_{G}}$ ${\displaystyle J}$ ${\displaystyle M}$ ${\displaystyle 0,\lambda _{2},\ldots ,\lambda _{n}}$ ${\displaystyle |1_{S}^{\operatorname {T} }M1_{T}|=\langle 1_{S},M1_{T}\rangle \leq \|1_{S}\|\|M1_{T}\|}$ ${\displaystyle M}$

${\displaystyle \|M1_{T}\|^{2}=\langle M1_{T},M1_{T}\rangle =\langle 1_{T},M^{2}1_{T}\rangle =\left\langle 1_{T},\sum _{i=1}^{n}M^{2}\langle 1_{T},v_{i}\rangle v_{i}\right\rangle =\sum _{i=2}^{n}\lambda _{i}^{2}\langle 1_{T},v_{i}\rangle ^{2}\leq \lambda ^{2}\|1_{T}\|^{2}}$ 。

これは、およびを意味します。 ${\displaystyle \|M1_{T}\|\leq \lambda \|1_{T}\|}$ ${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}}$

より厳しい境界の証明スケッチ

上記のより厳密な境界を示すために、代わりにベクトルとを考えます。これらは両方とも に垂直です。展開すると、 ${\displaystyle 1_{S}-{\frac {|S|}{n}}\mathbf {1} }$ ${\displaystyle 1_{T}-{\frac {|T|}{n}}\mathbf {1} }$ ${\displaystyle v_{1}}$

${\displaystyle 1_{S}^{\operatorname {T} }A_{G}1_{T}=\left({\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left({\frac {|T|}{n}}\mathbf {1} \right)+\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)}$

展開式の他の2つの項はゼロであるからです。最初の項は に等しいので、 ${\displaystyle {\frac {|S||T|}{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}}|S||T|}$

${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \left|\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)\right|}$

前の証明と同じ方法を使用し て、右側の境界を設定できます。${\displaystyle \lambda \left\|1_{S}-{\frac {|S|}{|n|}}\mathbf {1} \right\|\left\|1_{T}-{\frac {|T|}{|n|}}\mathbf {1} \right\|=\lambda {\sqrt {|S||T|\left(1-{\frac {|S|}{n}}\right)\left(1-{\frac {|T|}{n}}\right)}}}$

アプリケーション

拡張混合補題は、グラフ内の独立集合の大きさの上限を求めるのに用いることができる。特に、グラフ内の独立集合の大きさは最大で である。これは、上記の命題を代入し、次の事実を用いることで証明される。${\displaystyle (n,d,\lambda )}$ ${\displaystyle \lambda n/d.}$ ${\displaystyle T=S}$ ${\displaystyle e(S,S)=0.}$

追加の帰結として、 が-グラフである場合、その彩色数は少なくとも となります。これは、有効なグラフ彩色において、与えられた色の頂点の集合が独立集合となるためです。上記の事実により、各独立集合の大きさは最大で となるため、すべての頂点を覆うには少なくとも個の独立集合が必要となります。 ${\displaystyle G}$ ${\displaystyle (n,d,\lambda )}$ ${\displaystyle \chi (G)}$ ${\displaystyle d/\lambda .}$ ${\displaystyle \lambda n/d,}$ ${\displaystyle d/\lambda }$

拡張混合補題の2つ目の応用は、極性グラフ内の独立集合の最大可能サイズの上限を与えることである。極性を持つ有限射影平面 が与えられたとき、極性グラフとは、頂点が の点 a であり、頂点と が連結されていることが、かつその必要十分条件であるようなグラフである。特に、 が順序を持つ場合、拡張混合補題は、極性グラフ内の独立集合のサイズが最大でa であることを示すことができる。この上限は、ホバートとウィリフォードによって証明されている。 ${\displaystyle \pi }$ ${\displaystyle \perp ,}$ ${\displaystyle \pi }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\in y^{\perp }.}$ ${\displaystyle \pi }$ ${\displaystyle q,}$ ${\displaystyle q^{3/2}-q+2q^{1/2}-1,}$

コンバース

ビルとリニアルは^{[ 3 ]}逆も成り立つことを示した。つまり、 -正則グラフが任意 の2つの部分集合に対して${\displaystyle d}$ ${\displaystyle G=(V,E)}$ ${\displaystyle S,T\subseteq V}$ ${\displaystyle S\cap T=\emptyset }$

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

すると、その 2 番目に大きい (絶対値で) 固有値は で制限されます。 ${\displaystyle O(\lambda (1+\log(d/\lambda )))}$

ハイパーグラフへの一般化

フリードマンとウィドガーソンは、混合補題のハイパーグラフへの一般化を次のように証明した。

を-一様超グラフ、すなわちすべての「辺」が頂点の組である超グラフとする。任意の頂点の部分集合に対して、 ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle V_{1},...,V_{k}}$

${\displaystyle \left||e(V_{1},...,V_{k})|-{\frac {k!|E(H)|}{n^{k}}}|V_{1}|...|V_{k}|\right|\leq \lambda _{2}(H){\sqrt {|V_{1}|...|V_{k}|}}.}$

注記

1. ヴァダン、サリル (2009 年春)。「エキスパンダー グラフ」(PDF)。ハーバード大学。2019 年12 月 1 日に取得。
2. Haemers著「Interlacing Eigenvalues and Graphs」の定理5.1を参照
3. 展開子混合補題逆

参考文献

• アロン、N.; チュン、FRK (1988)、「線形サイズの許容ネットワークの明示的構築」、離散数学、72 ( 1–3 ): 15–19、CiteSeerX  10.1.1.300.7495、doi : 10.1016/0012-365X(88)90189-6。
• FC Bussemaker, DM Cvetković, JJ Seidel. 例外ルート系に関連するグラフ, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. János Bolyai (1978), 185-191.

• Haemers, WH (1979).設計とグラフ理論における固有値技法(PDF) (Ph.D.).
• Haemers, WH (1995)、「インターレース固有値とグラフ」、線形代数応用、226 : 593–616、doi : 10.1016/0024-3795(95)00199-2。

• Hoory, S.; Linial, N.; Wigderson, A. (2006)、「Expander Graphs and their Applications」（PDF） , Bull. Amer. Math. Soc. (NS) , 43 (4): 439– 561, doi : 10.1090/S0273-0979-06-01126-8。

• Friedman, J.; Widgerson, A. (1995)、「ハイパーグラフの第二固有値について」(PDF)、Combinatorica、15 (1): 43– 65、doi : 10.1007/BF01294459、S2CID  17896683。