拡張混合補題

エキスパンダー混合補題は、ある-正則グラフの辺がグラフ全体に均等に分布していることを直感的に述べています。特に、2 つの頂点サブセットと間の辺の数は、ランダム-正則グラフにおけるそれらの間の辺の期待数、つまり に常に近くなります。 ${\displaystyle d}$${\displaystyle S}$${\displaystyle T}$ ${\displaystyle d}$${\displaystyle {\frac {d}{n}}|S||T|}$

-グラフを、その隣接行列の固有値の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}$

を2部グラフとし、のすべての頂点がの頂点に隣接し、 のすべての頂点が の頂点に隣接しているとします。および とします。 とします。すると ${\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}\}\leq \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}|=|1_{S}\cdot M1_{T}|\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 であり、頂点と頂点が連結されている場合のみ、特に が順序を持つ場合、拡張混合補題は、極性グラフ内の独立集合のサイズが最大で になる可能性があることを示します。この上限は、Hobart と Williford によって証明されて います。${\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,}$

BiluとLinialは^[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}|}}.}$

• アロン、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。例外的なルートシステムに関連するグラフ、組合せ論 (Proc. Fifth Hungarian Colloq.、Keszthely、1976)、Colloq. Math. Soc. János Bolyai (1978) の第 18 巻、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)、「ハイパーグラフの 2 番目の固有値について」(PDF)、Combinatorica、15 (1): 43–65、doi :10.1007/BF01294459、S2CID  17896683。