lema de mezcla de expansores

De hecho, podemos demostrar que

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

utilizando técnicas similares. ^{[ 1 ]}

Para grafos birregulares , tenemos la siguiente variación, donde tomamos${\displaystyle \lambda }$ser el segundo autovalor más grande. ^{[ 2 ]}

Dejar${\displaystyle G=(L,R,E)}$sea ​​un grafo bipartito tal que cada vértice en${\displaystyle L}$está adyacente a${\displaystyle d_{L}}$vértices de${\displaystyle R}$y cada vértice en${\displaystyle R}$está adyacente a${\displaystyle d_{R}}$vértices de${\displaystyle L}$. Dejar${\displaystyle S\subseteq L,T\subseteq R}$con${\displaystyle |S|=\alpha |L|}$y${\displaystyle |T|=\beta |R|}$. Dejar${\displaystyle e(G)=|E(G)|}$. Entonces

${\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 }}\,.}$

Tenga en cuenta que${\displaystyle {\sqrt {d_{L}d_{R}}}}$es el mayor valor propio de${\displaystyle G}$.

Dejar${\displaystyle A_{G}}$sea ​​la matriz de adyacencia de${\displaystyle G}$y dejar${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{n}}$sean los valores propios de${\displaystyle A_{G}}$(estos valores propios son reales porque${\displaystyle A_{G}}$es simétrico). Sabemos que${\displaystyle \lambda _{1}=d}$con el vector propio correspondiente${\displaystyle v_{1}={\frac {1}{\sqrt {n}}}\mathbf {1} }$, la normalización del vector de todos unos. Definir${\displaystyle \lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}}$y tenga en cuenta que${\displaystyle \max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}=\lambda ^{2}\leq \lambda _{1}^{2}=d^{2}}$. Porque${\displaystyle A_{G}}$es simétrico, podemos elegir vectores propios${\displaystyle v_{2},\ldots,v_{n}}$de${\displaystyle A_{G}}$correspondientes a los valores propios${\displaystyle \lambda _{2},\ldots ,\lambda _{n}}$de modo que${\displaystyle \{v_{1},\ldots,v_{n}\}}$forma una base ortonormal de${\displaystyle \mathbf {R} ^{n}}$.

Dejar${\displaystyle J}$ser el${\displaystyle n\times n}$matriz de todos 1. Tenga en cuenta que${\displaystyle v_{1}}$es un vector propio de${\displaystyle J}$con valor propio${\displaystyle n}$y entre sí${\displaystyle v_{i}}$, siendo perpendicular a${\displaystyle v_{1}=\mathbf {1} }$, es un vector propio de${\displaystyle J}$con valor propio 0. Para un subconjunto de vértices${\displaystyle U\subsetequ V}$, dejar${\displaystyle 1_{U}}$sea ​​el vector columna con${\displaystyle v^{\text{th}}}$coordenada igual a 1 si${\displaystyle v\in U}$y 0 en caso contrario. Entonces,

${\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|}$.

Dejar${\displaystyle M=A_{G}-{\frac {d}{n}}J}$. Porque${\displaystyle A_{G}}$y${\displaystyle J}$comparten los autovectores, los autovalores de${\displaystyle M}$son${\displaystyle 0,\lambda _{2},\ldots ,\lambda _{n}}$. Por la desigualdad de Cauchy-Schwarz , tenemos que${\displaystyle |1_{S}^{\operatorname {T} }M1_{T}|=\langle 1_{S},M1_{T}\rangle \leq \|1_{S}\|\|M1_{T}\|}$Además, porque${\displaystyle M}$es autoadjunto, podemos escribir

${\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}}$.

Esto implica que${\displaystyle \|M1_{T}\|\leq \lambda \|1_{T}\|}$y${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}}$.

Para demostrar la cota más ajustada anterior, en su lugar consideramos los vectores${\displaystyle 1_{S}-{\frac {|S|}{n}}\mathbf {1} }$y${\displaystyle 1_{T}-{\frac {|T|}{n}}\mathbf {1} }$, que son ambas perpendiculares a${\displaystyle v_{1}}$Podemos expandirnos

${\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)}$

porque los otros dos términos de la expansión son cero. El primer término es igual a${\displaystyle {\frac {|S||T|}{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}}|S||T|}$, por lo que encontramos que

${\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|}$

Podemos delimitar el lado derecho mediante${\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)}}}$utilizando los mismos métodos que en la demostración anterior.