Lema de mezcla de expansores

El lema de mezcla de expansores establece intuitivamente que las aristas de ciertos grafos -regulares están distribuidas uniformemente a lo largo del grafo. En particular, la cantidad de aristas entre dos subconjuntos de vértices y siempre está cerca de la cantidad esperada de aristas entre ellos en un grafo -regular aleatorio , es decir . ${\displaystyle d}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle d}$ ${\displaystyle {\frac {d}{n}}|S||T|}$

d-Gráficos expansores regulares

Define un -grafo como un grafo -regular en vértices tales que todos los valores propios de su matriz de adyacencia excepto uno tienen valor absoluto como máximo. La -regularidad del grafo garantiza que su mayor valor absoluto de un valor propio es De hecho, el vector de todos los 1 es un vector propio de con valor propio , y los valores propios de la matriz de adyacencia nunca excederán el grado máximo de en valor absoluto. ${\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}$

Si fijamos y luego -grafos formamos una familia de grafos expansores con una brecha espectral constante . ${\displaystyle d}$ ${\displaystyle \lambda }$ ${\displaystyle (n,d,\lambda )}$

Declaración

Sea un -grafo. Para dos subconjuntos cualesquiera , sea el número de aristas entre S y T (contando las aristas contenidas en la intersección de S y T dos veces). Entonces ${\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|}}\,.}$

Límite más estricto

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]

Gráficos birregulares

Para los gráficos birregulares , tenemos la siguiente variación, donde tomamos como el segundo valor propio más grande. ^[2] ${\displaystyle \lambda }$

Sea un grafo bipartito tal que cada vértice en es adyacente a los vértices de y cada vértice en es adyacente a los vértices de . Sea con y . Sea . Entonces ${\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 }}\,.}$

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

Pruebas

Prueba de la primera afirmación

Sea la matriz de adyacencia de y sean los valores propios de (estos valores propios son reales porque es simétrica). Sabemos que con el vector propio correspondiente , la normalización del vector de todos los 1. Defina y observe que . Como es simétrica, podemos elegir vectores propios de correspondientes a valores propios de modo que forme una base ortonormal de . ${\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}}$

Sea la matriz de todos los 1. Nótese que es un vector propio de con valor propio y cada uno de los otros , al ser perpendicular a , es un vector propio de con valor propio 0. Para un subconjunto de vértices , sea el vector columna con coordenadas iguales a 1 si y 0 en caso contrario. Entonces, ${\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|}$.

Sea . Como y comparten vectores propios, los valores propios de son . Por la desigualdad de Cauchy-Schwarz , tenemos que . Además, como es autoadjunto, podemos escribir ${\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}}$.

Esto implica que y . ${\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|}}}$

Bosquejo de prueba de límite más estricto

Para mostrar el límite más estricto anterior, en su lugar, consideramos los vectores y , que son ambos perpendiculares a . Podemos desarrollar ${\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)}$

porque los otros dos términos del desarrollo son cero. El primer término es igual a , por lo que encontramos que ${\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|}$

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

Aplicaciones

El lema de mezcla de expansores se puede utilizar para limitar superiormente el tamaño de un conjunto independiente dentro de un grafo. En particular, el tamaño de un conjunto independiente en un -grafo es como máximo. Esto se demuestra dejando la afirmación anterior y utilizando el hecho de que ${\displaystyle (n,d,\lambda )}$ ${\displaystyle \lambda n/d.}$ ${\displaystyle T=S}$ ${\displaystyle e(S,S)=0.}$

Una consecuencia adicional es que, si es un -grafo, entonces su número cromático es al menos Esto se debe a que, en una coloración de grafos válida, el conjunto de vértices de un color dado es un conjunto independiente. Por el hecho anterior, cada conjunto independiente tiene un tamaño como máximo , por lo que se necesitan al menos dichos conjuntos para cubrir todos los vértices. ${\displaystyle G}$ ${\displaystyle (n,d,\lambda )}$ ${\displaystyle \chi (G)}$ ${\displaystyle d/\lambda .}$ ${\displaystyle \lambda n/d,}$ ${\displaystyle d/\lambda }$

Una segunda aplicación del lema de mezcla de expansores es proporcionar un límite superior al tamaño máximo posible de un conjunto independiente dentro de un grafo de polaridad. Dado un plano proyectivo finito con una polaridad , el grafo de polaridad es un grafo donde los vértices son los puntos a de , y los vértices y están conectados si y solo si En particular, si tiene orden , entonces el lema de mezcla de expansores puede mostrar que un conjunto independiente en el grafo de polaridad puede tener un tamaño como máximo de un límite demostrado por Hobart y 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,}$

Conversar

Bilu y Linial demostraron ^[3] que también se cumple una regla inversa: si un grafo -regular satisface que para cualesquiera dos subconjuntos con tenemos ${\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|}},}$

entonces su segundo valor propio más grande (en valor absoluto) está limitado por . ${\displaystyle O(\lambda (1+\log(d/\lambda )))}$

Generalización a hipergrafos

Friedman y Widgerson demostraron la siguiente generalización del lema de mezcla a los hipergrafos.

Sea un hipergrafo -uniforme, es decir, un hipergrafo en el que cada "arista" es una tupla de vértices. Para cualquier elección de subconjuntos de vértices, ${\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}|}}.}$

Notas

1. Vadhan, Salil (primavera de 2009). "Gráficos de expansión" (PDF) . Universidad de Harvard . Consultado el 1 de diciembre de 2019 .
2. Véase el teorema 5.1 en "Entrelazando valores propios y gráficos" de Haemers
3. Lema de mezcla de expansores inverso

Referencias

• Alon, N.; Chung, FRK (1988), "Construcción explícita de redes tolerantes de tamaño lineal", Discrete Mathematics , 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. Gráficos relacionados con sistemas de raíces excepcionales, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volumen 18 de Colloq. Math. Soc. János Bolyai (1978), 185-191.

• Haemers, WH (1979). Técnicas de valores propios en diseño y teoría de grafos (PDF) (Ph.D.).
• Haemers, WH (1995), "Entrelazamiento de valores propios y gráficos", Linear Algebra Appl. , 226 : 593–616, doi : 10.1016/0024-3795(95)00199-2.

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Gráficos expansores y sus aplicaciones" (PDF) , Bull. Amer. Math. Soc. (NS) , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8.

• Friedman, J.; Widgerson, A. (1995), "Sobre el segundo valor propio de los hipergrafos" (PDF) , Combinatorica , 15 (1): 43–65, doi :10.1007/BF01294459, S2CID  17896683.