Gráfico expansor

La expansión de aristas (también número isoperimétrico o constante de Cheeger ) h ( G ) de un grafo G en n vértices se define como

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

dónde${\displaystyle \partial S:=\{\{u,v\}\in E(G)\$ :\ u\in S,v\notin S\},}

que también se puede escribir como ∂ S = E ( S , S ) con S  := V ( G ) \ S el complemento de S y

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\$ :\ u\in A,v\in B\}}

las aristas entre los subconjuntos de vértices A , B ⊆ V ( G ) .

En la ecuación, el mínimo se encuentra sobre todos los conjuntos no vacíos S de como máximo n / 2 vértices y ∂ S es el límite de aristas de S , es decir, el conjunto de aristas con exactamente un extremo en S. ^{[ 2 ]}

Intuitivamente,

${\displaystyle \min {|\partial S|}=\min |E({S},{\overline {S}})|}$

es el número mínimo de aristas que deben cortarse para dividir el grafo en dos. La expansión de aristas normaliza este concepto dividiendo por el menor número de vértices entre las dos partes. Para ver cómo la normalización puede cambiar drásticamente el valor, consideremos el siguiente ejemplo. Tomemos dos grafos completos con el mismo número de vértices n y agreguemos n aristas entre los dos grafos conectando sus vértices uno a uno. El corte mínimo será n, pero la expansión de aristas será 1.

Nótese que en min | ∂ S | , la optimización se puede realizar de forma equivalente sobre 0 ≤ | S | ≤ n ⁄ 2 o sobre cualquier subconjunto no vacío, ya que ${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$. Lo mismo no es cierto para h ( G ) debido a la normalización por | S | . Si queremos escribir h ( G ) con una optimización sobre todos los subconjuntos no vacíos, podemos reescribirlo como

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {|E({S},{\overline {S}})|}{\min\{|S|,|{\overline {S}}|\}}}.}$

El número isoperimétrico de vértices h _out ( G ) (también expansión o magnificación de vértices ) de un grafo G se define como

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

donde ∂ _out ( S ) es el límite exterior de S , es decir, el conjunto de vértices en V ( G ) \ S con al menos un vecino en S . ^{[ 3 ]} En una variante de esta definición (llamada expansión de vecino único ) ∂ _out ( S ) se reemplaza por el conjunto de vértices en V con exactamente un vecino en S . ^{[ 4 ]}

El número isoperimétrico de vértices h _en ( G ) de un grafo G se define como

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

dónde${\displaystyle \partial _{\text{in}}(S)}$es el límite interior de S , es decir, el conjunto de vértices en S con al menos un vecino en V ( G ) \ S . ^{[ 3 ]}

Cuando G es d -regular , es posible una definición algebraica lineal de expansión basada en los valores propios de la matriz de adyacencia A = A ( G ) de G , donde A _ij es el número de aristas entre los vértices i y j . ^{[ 5 ]} Debido a que A es simétrica , el teorema espectral implica que A tiene n valores propios reales λ ₁ ≥ λ ₂ ≥ … ≥ λ _n . Se sabe que todos estos valores propios están en [− d , d ] y más específicamente, se sabe que λ _n = − d si y solo si G es bipartita.

De manera más formal, nos referimos a un grafo d -regular de n vértices con

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

como un ( n , d , λ ) - grafo . La cota dada por un ( n , d , λ ) - grafo en λ _i para i ≠ 1 es útil en muchos contextos, incluido el lema de mezcla de expansores .

La expansión espectral puede ser bilateral , como se indicó anteriormente, con${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$, o puede ser unilateral , con${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$. Esta última es una noción más débil que también se cumple para grafos bipartitos y sigue siendo útil para muchas aplicaciones, como el lema de Alon-Chung. ^{[ 6 ]}

Debido a que G es regular, la distribución uniforme${\displaystyle u\in \mathbb {R} ^{n}}$con u _i = 1 ⁄ n para todo i = 1, …, n es la distribución estacionaria de G. Es decir, tenemos Au = du , y u es un vector propio de A con valor propio λ ₁ = d , donde d es el grado de los vértices de G. La brecha espectral de G se define como d − λ _{2 , y mide la} ^expansión espectral del grafo G. ^{[ 7} ]

Si establecemos

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

Como este es el mayor valor propio correspondiente a un vector propio ortogonal a u , se puede definir de forma equivalente utilizando el cociente de Rayleigh :

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

dónde

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

es la norma 2 del vector${\displaystyle v\in \mathbb {R} ^{n}}$.

Las versiones normalizadas de estas definiciones también son ampliamente utilizadas y más convenientes para enunciar algunos resultados. Aquí se considera la matriz ⁠ 1 / d ⁠ A , que es la matriz de transición de Markov del grafo G . Sus autovalores están entre −1 y 1. Para grafos no necesariamente regulares, el espectro de un grafo puede definirse de manera similar utilizando los autovalores de la matriz laplaciana . Para grafos dirigidos , se consideran los valores singulares de la matriz de adyacencia A , que son iguales a las raíces de los autovalores de la matriz simétrica A ^T A .

Una familia${\displaystyle (G_{i})_{i\in \mathbb {N} }}$de${\displaystyle d}$-gráficos regulares de tamaño creciente es una familia de expansores si${\displaystyle h(G_{i})}$está acotado lejos de cero. ^{[ 8 ]}

Cuando G es d -regular, es decir _, cada vértice tiene grado d , existe una relación entre la constante isoperimétrica h ( G ) y la brecha d − λ2 en el espectro del operador de adyacencia de G. Según la teoría espectral de grafos estándar, el autovalor trivial del operador de adyacencia de un grafo d-regular es λ1 = d y el primer autovalor _no trivial es λ2 _. Si G es conexo, entonces λ2 < d . Una desigualdad debida a Dodziuk ^[ ₉ ^] e independientemente a Alon y Milman ^{[ 10 ]} establece que ^{[ 11 ] .}

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

De hecho, el límite inferior es ajustado. El límite inferior se alcanza en el límite para el hipercubo Q _n , donde h ( G ) = 1 y d – λ ₂ = 2 . El límite superior se alcanza (asintóticamente) para un ciclo, donde h ( C _n ) = 4/ n = Θ(1/ n ) y d – λ ₂ = 2 – 2cos(2${\displaystyle \pi }$/ n ) ≈ (2${\displaystyle \pi }$/ n ) ² = Θ(1/ n ² ) . ^{[ 1 ] En [ 12 ]} se da una mejor cota como

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

Estas desigualdades están estrechamente relacionadas con la cota de Cheeger para cadenas de Markov y pueden verse como una versión discreta de la desigualdad de Cheeger en geometría riemanniana .

También se han estudiado conexiones similares entre los números isoperimétricos de vértice y la brecha espectral: ^{[ 13 ]}

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

Asintóticamente hablando, las cantidades h ² ⁄ d , h _out , y h _in ² están todas acotadas superiormente por la brecha espectral O ( d – λ ₂ ) .

Se conocen construcciones algebraicas basadas en grafos de Cayley para diversas variantes de grafos expansores. La siguiente construcción se debe a Margulis y ha sido analizada por Gabber y Galil. ^{[ 16 ]} Para cada número natural n , se considera el grafo G _n con el conjunto de vértices${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, dónde${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$: Para cada vértice${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, sus ocho vértices adyacentes son

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

Entonces se cumple lo siguiente:

Teorema. Para todo n , el grafo G _n tiene el segundo mayor valor propio.${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$.

Según un teorema de Alon y Boppana , todos los grafos d -regulares suficientemente grandes satisfacen${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$, donde λ ₂ es el segundo autovalor más grande en valor absoluto. ^{[ 17 ]} Como consecuencia directa, sabemos que para cada d fijo y${\displaystyle \lambda <2{\sqrt {d-1}}}$, solo hay un número finito de ( n , d , λ ) -grafos. Los grafos de Ramanujan son grafos d -regulares para los cuales esta cota es ajustada, satisfaciendo ^{[ 18 ]}

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

Por lo tanto, los gráficos de Ramanujan tienen un valor asintóticamente mínimo posible de λ ₂ . Esto los convierte en excelentes expansores espectrales.

Lubotzky , Phillips y Sarnak (1988), Margulis (1988) y Morgenstern (1994) muestran cómo se pueden construir explícitamente los grafos de Ramanujan. ^{[ 19 ]}

En 1985, Alon conjeturó que la mayoría de los grafos d- regulares con n vértices, para n suficientemente grande , son casi Ramanujan. ^{[ 20 ]} Es decir, para ε > 0 , satisfacen

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$.

En 2003, Joel Friedman demostró la conjetura y especificó qué se entiende por " grafos d -regulares más comunes" al demostrar que los grafos d -regulares aleatorios tienen${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$para cada ε > 0 con probabilidad 1 – O ( n ^-τ ) , donde ^{[ 21 ] [ 22 ]}

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

Puder dio una demostración más sencilla de un resultado ligeramente más débil. ^{[ 23 ] [ 24 ] [ 25 ]}

Marcus , Spielman y Srivastava , ^{[ 26 ] [ 27 ]} dieron una construcción de grafos bipartitos de Ramanujan basados ​​en elevaciones .

En 2024, una preimpresión de Jiaoyang Huang, Theo McKenzie y Horng-Tzer Yau demostró que

${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$.

con la fracción de valores propios que alcanzan el límite de Alon-Boppana aproximadamente 69% de probar que se cumple la universalidad de borde , es decir, siguen una distribución de Tracy-Widom asociada con el conjunto ortogonal gaussiano ^{[ 28 ] [ 29 ]}

Reingold , Vadhan y Wigderson introdujeron el producto zigzag en 2000. ^{[ 30 ]} En términos generales, el producto zigzag de dos grafos expansores produce un grafo con una expansión solo ligeramente peor. Por lo tanto, un producto zigzag también puede usarse para construir familias de grafos expansores. Si G es un grafo ( n , d , λ ₁ ) y H es un grafo ( m , d , λ ₂ ) , entonces el producto zigzag G ◦ H es un grafo ( nm , d ² , φ ( λ ₁ , λ ₂ )) donde φ tiene las siguientes propiedades.

1. Si λ ₁ < 1 y λ ₂ < 1 , entonces φ ( λ ₁ , λ ₂ ) < 1 ;
2. φ ( λ ₁ , λ ₂ ) ≤ λ ₁ + λ ₂ .

Específicamente, ^{[ 30 ]}

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

Nótese que la propiedad (1) implica que el producto en zigzag de dos grafos expansores también es un grafo expansor, por lo que los productos en zigzag se pueden usar inductivamente para crear una familia de grafos expansores.

Intuitivamente, la construcción del producto en zigzag puede pensarse de la siguiente manera. Cada vértice de G se expande en una "nube" de m vértices, cada uno asociado a una arista diferente conectada al vértice. Cada vértice ahora se etiqueta como ( v , k ) , donde v se refiere a un vértice original de G y k se refiere a la k -ésima arista de v . Dos vértices, ( v , k ) y ( w , ℓ ), están conectados si es posible ir de ( v , k ) a ( w , ℓ ) a través de la siguiente secuencia de movimientos.

1. Zig – Muévase de ( v , k ) a ( v , k' ) , usando una arista de H.
2. Salta a través de las nubes usando el borde k' en G para llegar a ( w , ℓ ' ) .
3. Zag – Muévase de ⁽ w , ℓ ′ ) a ( w , ℓ ) usando una arista de H. [ ^{30 ]}

Un r -lift de un grafo se forma reemplazando cada vértice por r vértices y cada arista por un emparejamiento entre los conjuntos correspondientes de${\displaystyle r}$vértices. El grafo elevado hereda los autovalores del grafo original y tiene algunos autovalores adicionales. Bilu y Linial ^{[ 31 ] [ 32 ]} demostraron que todo grafo d -regular tiene un 2-lift en el que los autovalores adicionales son como máximo${\displaystyle O({\sqrt {d\log ^{3}d}})}$en magnitud. También demostraron que si el grafo inicial es un expansor suficientemente bueno, entonces se puede encontrar un buen 2-lift en tiempo polinomial , lo que proporciona una construcción eficiente de expansores d -regulares para cada d .

Bilu y Linial conjeturaron que el límite${\displaystyle O({\sqrt {d\log ^{3}d}})}$puede mejorarse a${\displaystyle 2{\sqrt {d-1}}}$, lo cual sería óptimo debido a la cota de Alon-Boppana . Esta conjetura fue demostrada en el contexto bipartito por Marcus , Spielman y Srivastava , ^{[ 26 ] [ 27 ]} quienes utilizaron el método de entrelazamiento de polinomios. Como resultado, obtuvieron una construcción alternativa de grafos de Ramanujan bipartitos . La demostración no constructiva original fue convertida en un algoritmo por Michael B. Cohen. ^{[ 33 ]} Posteriormente, el método fue generalizado a r -lifts por Hall, Puder y Sawin. ^{[ 34 ]}

Hay muchos resultados que muestran la existencia de grafos con buenas propiedades de expansión a través de argumentos probabilísticos. De hecho, la existencia de expansores fue probada por primera vez por Pinsker ^{[ 35 ]} quien mostró que para un grafo bipartito regular d de n vértices elegidos aleatoriamente , | N ( S ) | ≥ ( d – 2) | S | para todos los subconjuntos de vértices | S | ≤ c _d n con alta probabilidad , donde c _d es una constante que depende de d que es O ( d ^{- 4} ) . Alon y Roichman ^{[ 36 ]} mostraron que para cada 1 > ε > 0 , hay algún c ( ε ) > 0 tal que se cumple lo siguiente: Para un grupo G de orden n , considere el grafo de Cayley en G con c ( ε ) log ₂ n elementos elegidos aleatoriamente de G. Entonces, en el límite de n tendiendo a infinito, el grafo resultante es casi seguramente un ε- expansor.

En 2021, Alexander modificó un algoritmo MCMC para buscar construcciones aleatorias que produjeran grafos de Ramanujan con un tamaño de vértice y un grado de regularidad fijos. ^{[ 37 ]} Los resultados muestran que existen grafos de Ramanujan para cada par de tamaño de vértice y grado hasta 2000 vértices.

En 2024, Alon elaboró ​​una construcción explícita para grafos cercanos a Ramanujan de cada par de tamaño de vértice y grado.

El lema de mezcla de expansores establece que para un grafo ( n , d , λ ) , para cualesquiera dos subconjuntos de los vértices S , T ⊆ V , el número de aristas entre S y T es aproximadamente el que se esperaría en un grafo d- regular aleatorio. La aproximación es mejor cuanto menor sea λ . En un grafo d- regular aleatorio, así como en un grafo aleatorio de Erdős-Rényi con probabilidad de arista d ⁄ n , esperamos d ⁄ n • | S | • | T | aristas entre S y T .

De manera más formal, sea E ( S , T ) el número de aristas entre S y T . Si los dos conjuntos no son disjuntos, las aristas en su intersección se cuentan dos veces, es decir,

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

Entonces, el lema de mezcla de expansores dice que se cumple la siguiente desigualdad:

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

Muchas propiedades de los ( n , d , λ ) -grafos son corolarios de los lemas de mezcla de expansores, incluyendo los siguientes. ^{[ 1 ]}

• Un conjunto independiente de un grafo es un subconjunto de vértices sin dos vértices adyacentes. En un grafo ( n , d , λ ) , un conjunto independiente tiene un tamaño como máximo λn ⁄ d .
• El número cromático de un grafo G , χ ( G ) , es el número mínimo de colores necesarios para que los vértices adyacentes tengan colores diferentes. Hoffman demostró que d / λ ≤ χ ( G ) , ^{[ 38 ]} mientras que Alon, Krivelevich y Sudakov demostraron que si d < 2n / 3 , ^entonces [ ^{39 ]}

${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• El diámetro de un grafo es la distancia máxima entre dos vértices, donde la distancia entre dos vértices se define como el camino más corto entre ellos. Chung demostró que el diámetro de un grafo ( n , d , λ ) es como máximo ^{[ 40 ].}

${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

La cota de Chernoff establece que, al muestrear muchas muestras independientes de una variable aleatoria en el intervalo [−1, 1] , con alta probabilidad el promedio de nuestras muestras se aproxima a la esperanza de la variable aleatoria. El lema de muestreo de caminata expansora, debido a Ajtai, Komlós y Szemerédi (1987) y Gillman (1998) , establece que esto también se cumple al muestrear a partir de una caminata en un grafo expansor. Esto es particularmente útil en la teoría de la desaleatorización , ya que el muestreo según una caminata expansora utiliza muchos menos bits aleatorios que el muestreo independiente.

Las redes de ordenación toman un conjunto de entradas y realizan una serie de pasos paralelos para ordenarlas. Un paso paralelo consiste en realizar cualquier número de comparaciones disjuntas y, potencialmente, intercambiar pares de entradas comparadas. La profundidad de una red viene dada por el número de pasos paralelos que realiza. Los grafos expansores desempeñan un papel importante en la red de ordenación AKS, que alcanza una profundidad de O (log n ) . Si bien esta es asintóticamente la mejor profundidad conocida para una red de ordenación, la dependencia de los expansores hace que el límite constante sea demasiado grande para su uso práctico.

Dentro de la red de ordenación AKS, se utilizan grafos expansores para construir ε -mitads de profundidad limitada. Un ε -mitad toma como entrada una permutación de longitud n de (1, …, n ) y divide las entradas por la mitad en dos conjuntos disjuntos A y B, de modo que para cada entero k ≤ n / 2, como máximo εk de las k entradas más pequeñas están en B y como máximo εk de las k entradas más grandes están en A. Los conjuntos A y B constituyen una ε -mitad.

Siguiendo a Ajtai, Komlós y Szemerédi (1983) , un ε -halver de profundidad d se puede construir de la siguiente manera. Tomar un expansor bipartito de n vértices y grado d con partes X e Y de igual tamaño tal que cada subconjunto de vértices de tamaño como máximo εn tenga al menos 1 – ε / ε vecinos .

Los vértices del grafo pueden considerarse registros que contienen entradas, y las aristas, cables que comparan las entradas de dos registros. Al principio, se colocan arbitrariamente la mitad de las entradas en X y la otra mitad en Y , y se descomponen las aristas en d emparejamientos perfectos. El objetivo es que X contenga aproximadamente la mitad menor de las entradas e Y la mitad mayor. Para lograrlo, se procesa cada emparejamiento secuencialmente comparando los registros emparejados por las aristas y corrigiendo las entradas que estén fuera de orden. Específicamente, para cada arista del emparejamiento, si la entrada mayor está en el registro de X y la menor en el de Y , se intercambian las entradas de manera que la menor esté en X y la mayor en Y. Es evidente que este proceso consta de d pasos paralelos.

Después de todas las d rondas, tome A como el conjunto de entradas en los registros en X y B como el conjunto de entradas en los registros en Y para obtener una ε -división. Para ver esto, observe que si un registro u en X y v en Y están conectados por una arista uv, entonces después de que se procesa la coincidencia con esta arista, la entrada en u es menor que la de v . Además, esta propiedad permanece verdadera durante el resto del proceso. Ahora, supongamos que para algún k ≤ n ⁄ 2 que más de εk de las entradas (1, …, k ) están en B . Entonces por propiedades de expansión del grafo, los registros de estas entradas en Y están conectados con al menos ⁠ 1 – ε / ε ⁠ k registros en X . En total, esto constituye más de k registros, por lo que debe haber algún registro A en X conectado a algún registro B en Y tal que la entrada final de A no esté en (1, …, k ) , mientras que la entrada final de B sí lo esté. Sin embargo, esto viola la propiedad anterior y, por lo tanto, los conjuntos de salida A y B deben ser una reducción a la mitad de ε .