Gráfico de expansión

En la teoría de grafos, un gráfico de expansión es un gráfico disperso que tiene fuertes propiedades de conectividad, cuantificadas mediante expansión de vértice, borde o espectral. Las construcciones de expansores han generado investigaciones en matemáticas puras y aplicadas, con varias aplicaciones a la teoría de la complejidad, el diseño de redes informáticas robustas y la teoría de los códigos de corrección de errores.

Definiciones

Intuitivamente, un gráfico de expansión es un multigrafo no dirigido finito en el que cada subconjunto de vértices que no es "demasiado grande" tiene un "grande" Perímetro. Las diferentes formalizaciones de estas nociones dan lugar a diferentes nociones de expansores: expansores de borde, expansores de vértices y expansores espectrales, tal como se definen a continuación.

Un gráfico desconectado no es un expansor, ya que el límite de un componente conectado está vacío. Cada gráfico conexo es un expansor; sin embargo, diferentes gráficos conectados tienen diferentes parámetros de expansión. El gráfico completo tiene la mejor propiedad de expansión, pero tiene el mayor grado posible. Informalmente, un gráfico es un buen expansor si tiene parámetros de expansión altos y de bajo grado.

Expansión de borde

La expansión del borde (también número isoperimétrico o constante de Cheeger) h(G< /i>) de un gráfico G en n vértices se define como

${displaystyle h(G)=min - ¿Por qué? {n}{2}{frac} {parial S turba} {fnMicrosoft Sans Serif}$

Donde ${displaystyle partial S:={u,v}in E(G):uin S,vin V(G)setminus 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): ¿Qué?$

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

En la ecuación, el mínimo es sobre todos los conjuntos no vacíos S de como máximo < abarcan clase="frac" rol="matemáticas">n⁄2 vértices y ∂S es el límite del borde de S, es decir, el conjunto de bordes con exactamente un punto final en S.

Intuitivamente,

${displaystylemin {partial Stención}=min E({S},{overline {S}}}$

es el número mínimo de bordes que deben cortarse para dividir el gráfico en dos. La expansión de borde normaliza este concepto dividiendo con el menor número de vértices entre las dos partes. Para ver cómo la normalización puede cambiar drásticamente el valor, considere el siguiente ejemplo. Toma dos gráficos completos con el mismo número de vértices n y agrega n bordes entre los dos gráficos conectando sus vértices uno a uno. El corte mínimo será n pero la expansión del borde será 1.

Observe que en min |∂S|, la optimización se puede realizar de manera equivalente sobre 0 ≤ |E| ≤ n⁄2 o sobre cualquier subconjunto no vacío, ya que E(S< /i>, S) = E(S, < i>S). No ocurre lo mismo con h(G) debido a la normalización por parte de | 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 Ssubsetneq V(G)}{frac {E({S},{overline {S}}}}{min{ vidasfnMicrosoft Sans, {S}tuvo.}}$

Expansión de vértice

El número isoperimétrico del vértice h_out(G) (también expansión de vértice o aumento) de un gráfico G Se define como

${displaystyle h_{text{out}(G)=min - ¿Por qué? {fn}{f} {fnK} {fnK} {fnfnh00} {fnh00}} {fnh00}}}}$

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. 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.

El número isoperimétrico del vértice h_in(G) de un gráfico G se define como

${displaystyle h_{text{in}(G)=min - ¿Por qué? {n}{2}{frac} ¿Qué?$

Donde ${displaystyle partial _{in}(S)}$ es límite interior de S, es decir, el conjunto de vértices en S con al menos un vecino V()G) S.

Expansión espectral

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 < abarcan clase="texhtml">A = A(G) de G, donde A_ij es el número de aristas entre los vértices i y j< /lapso>. Debido a que A es simétrico, el teorema espectral implica que A tiene n valores propios con valores reales λ_{1< /sub> ≥ λ2 ≥ … ≥ λn}. Se sabe que todos estos autovalores están en [−d, d] y más específicamente, se sabe que < span class="texhtml">λ_n = −d si y solo si G es bipartito.

Más formalmente, nos referimos a un n-vértice, d-gráfico regular con

${displaystyle max _{ineq 1} _{i}Sobrevivirleq lambda$

como un (n, d, λ)-gráfico. El límite dado por un gráfico (n, d, λ) en λ _i para i ≠ 1 es útil en muchos contextos, incluido el expansor lema de mezcla.

Porque... G es regular, la distribución uniforme ${displaystyle uin mathbb {R} {fn}$ con u_i = 1.n para todos i = 1,... n es la distribución estacionaria de G. Es decir, tenemos Au = du, y u es un eigenvector de A con eigenvalue λ₁ = d, donde d es el grado de los vértices G. El brecha espectral de G se define como d − λ₂, y mide la expansión espectral del gráfico G.

Si establecemos

${displaystyle lambda =max{ Anteriorlambda _{2} aguanta, aguanta - Hola.$

como este es el valor propio más grande correspondiente a un vector propio ortogonal a u, se puede definir de manera equivalente usando el cociente de Rayleigh:

${displaystyle lambda =max _{vperp u,vneq 0}{frac { eternaAv eterna_{2}}{v eterna_{2}}}}}$

dónde

${displaystyle Toddvfn_{2}=left(sum) ¿Qué?$

es el 2-norm del vector ${displaystyle vin mathbb {R} {fn}$.

Las versiones normalizadas de estas definiciones también se usan ampliamente y son más convenientes para establecer algunos resultados. Aquí se considera la matriz 1 //span>dA, que es la matriz de transición de Markov del gráfico G. Sus valores propios están entre -1 y 1. Para gráficos no necesariamente regulares, el espectro de un gráfico se puede definir de manera similar utilizando los valores propios 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 valores propios de la simétrica matriz A^TA.

Relaciones entre diferentes propiedades de expansión

Los parámetros de expansión definidos anteriormente están relacionados entre sí. En particular, para cualquier gráfico d-regular G,

${displaystyle h_{text{out}(G)leq h(G)leq dcdot h_{text{out}(G).}$

En consecuencia, para gráficos de grado constante, la expansión de vértice y borde son cualitativamente iguales.

Desigualdades Cheeger

Cuando G es d< /span>-regular, lo que significa que cada vértice es de grado d, existe una relación entre la constante isoperimétrica h(G) y la brecha d − λ₂ en el espectro del operador de adyacencia de G. Según la teoría de gráficos espectrales estándar, el valor propio trivial del operador de adyacencia de un gráfico d-regular es λ₁ = d y el primer valor propio no trivial es λ₂. Si G está conectado, entonces λ₂ < d. Una desigualdad debida a Dodziuk e independientemente Alon y Milman afirman que

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

De hecho, el límite inferior está apretado. El límite inferior se alcanza en límite para el hipercubo Q_n, donde h()G) = 1 y d – λ = 2. El límite superior se logra (asintóticamente) para un ciclo, donde H()C_n) = 4/n= 1/n) y d – λ = 2-2cos(2${displaystyle pi}$/nEntendido (2)${displaystyle pi}$/n)^2= Despierta(1/n²). Un límite mejor se da como

${displaystyle h(G)leq {sqrt {d^{2}-lambda - ¿Qué?$

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

También se han estudiado conexiones similares entre los números isoperimétricos de vértices y la brecha espectral:

${displaystyle h_{text{out}}(G)leq left({sqrt {4(d-lambda) ¿Qué?$

${displaystyle h_{text{in}(G)leq {sqrt {8(d-lambda - Sí.$

Hablando asintóticamente, las cantidades h^{2< /sup>}⁄d, h< /i>_fuera y h_dentro²< /span> están limitados arriba por la brecha espectral O(d – λ₂).

Construcciones

Hay tres estrategias generales para construir explícitamente familias de gráficos de expansión. La primera estrategia es algebraica y teórica de grupos, la segunda estrategia es analítica y usa combinatoria aditiva, y la tercera estrategia es combinatoria y usa el zig-zag y productos gráficos relacionados. Noga Alon mostró que ciertos gráficos construidos a partir de geometrías finitas son los ejemplos más escasos de gráficos de gran expansión.

Margulis–Gabber–Galil

Las construcciones algebraicas basadas en los gráficos de Cayley son conocidas por varias variantes de gráficos de expansión. La siguiente construcción se debe a Margulis y ha sido analizada por Gabber y Galil. Por cada número natural n, uno considera el gráfico G_n con el vertex fijado ${displaystyle mathbb {Z} _{n}times mathbb {Z} _{n}$, donde ${displaystyle mathbb {Z} _{n}=mathbb {Z} /nmathbb {Z}$Por cada vértice ${displaystyle (x,y)in mathbb {Z} _{n}times mathbb {Z} _{n}$, sus ocho vértices adyacentes son

${displaystyle (xpm 2y,y),(xpm (2y+1),y),(x,ypm 2x),(x,ypm (2x+1)). }$

Entonces se cumple lo siguiente:

Teorema. Para todos n, el gráfico G_n tiene segundo eigenvalue más grande ${displaystyle lambda (G)leq 5{sqrt {2}}$.

Gráficos de Ramanujan

Por un teorema de Alon y Boppana, todo lo suficientemente grande d- gráficos regulares satisfacer ${displaystyle lambda _{2}geq 2{sqrt {d-1}-o(1)}$, donde λ₂ es el segundo eigenvalue más grande en valor absoluto. Como consecuencia directa, sabemos que por cada fijo d y ${displaystyle lambda 2{sqrt {d-1}}$ sólo hay finitos ()n, d, λ)- Gráficos. Los gráficos de Ramanujan son d-grafos regulares para los cuales este límite es apretado, satisfactorio

${displaystyle lambda =max _{ hospitallambda _{i} invisibled ¿Qué?$

Por lo tanto, los gráficos de Ramanujan tienen un valor asintóticamente más pequeño 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 gráficos de Ramanujan de forma explícita.

En 1985, Alon conjeturó que la mayoría de los gráficos d-regulares en n vértices, para n suficientemente grandes, son casi Ramanujan. Es decir, para φ > 0, satisfacen

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

En 2003, Joel Friedman probó la conjetura y especificó lo que significa "la mayoría" d-grafos regulares" mostrando que los gráficos aleatorios d-regulares tienen ${displaystyle lambda leq 2{sqrt {d-1}+varepsilon }$ para todos φ ■ 0 con probabilidad 1 – O()n^τ), donde

${displaystyle tau =leftlceil {fnMicroc {fnMicroc} Está bien.$

Producto Zig-Zag

Reingold, Vadhan y Wigderson introdujeron el producto en zig-zag en 2003. En términos generales, el producto en zig-zag de dos gráficos de expansión produce un gráfico con una expansión ligeramente peor. Por lo tanto, también se puede usar un producto en zig-zag para construir familias de gráficos de expansión. Si G es una (n, m< /i>, λ₁)-graph y H es una (m, d, λ₁)-graph, luego el producto en zig-zag G ◦ H es una (nm, d ², φ(λ₁, λ₂))-gráfico donde φ tiene las siguientes propiedades.

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

Específicamente,

${displaystyle f(lambda _{1},lambda _{2}={frac {1}{2}} {1-lambda ¿Qué? ##{2}+{frac {1}{2}{sqrt {(1-lambda ################################################################################################################################################################################################################################################################ ##{1}{2}+4lambda - ¿Qué?$

Tenga en cuenta que la propiedad (1) implica que el producto en zig-zag de dos gráficos de expansión también es un gráfico de expansión, por lo que los productos en zig-zag se pueden usar de manera inductiva para crear una familia de gráficos de expansión.

Intuitivamente, la construcción del producto en zig-zag se puede pensar de la siguiente manera. Cada vértice de G se convierte en una "nube" de m vértices, cada uno asociado a una arista diferente conectada al vértice. Cada vértice ahora está etiquetado como (v, k) donde v se refiere a un vértice original de G y k hace referencia al késimo borde de v. Dos vértices, (v, k) y (w,l) están conectados si es posible obtenerlos desde (v, k) a (w, l) a través de la siguiente secuencia de movimientos.

1. Zig - Muévete. ()v, k) a ()v, k ' ), usando un borde de H.
2. Saltar a través de las nubes usando el borde k ' dentro G para llegar ()w, l ' ).
3. Zag - Muévete. ()w, l ' ) a ()w, l) usando un borde H.

Construcciones aleatorias

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, quien demostró que para un n vértice elegido al azar, a la izquierda d gráfico bipartito regular, |N(S)| ≥ (d – 2)|S| para todos los subconjuntos de vértices | S| ≤ c_dn con alta probabilidad, donde c _d es una constante que depende de d que es O(d^-4). Alon y Roichman demostraron que para cada grupo G de orden n y cada 1 > ε > 0, hay algo de c(ε) > 0 tal que el gráfico de Cayley en G con c(ε) log₂ n generadores es un ε expansor, es decir, tiene un segundo valor propio menor que 1 – ε , con alta probabilidad.

Aplicaciones y propiedades útiles

La motivación original de los expansores es construir redes robustas y económicas (teléfono o computadora): un expansor con grado acotado es precisamente un gráfico robusto asintótico con el número de aristas creciendo linealmente con el tamaño (número de vértices), para todos los subconjuntos.

Los gráficos de expansión han encontrado amplias aplicaciones en informática, en el diseño de algoritmos, códigos de corrección de errores, extractores, generadores pseudoaleatorios, redes de clasificación (Ajtai, Komlós & Szemerédi (1983)) y redes informáticas sólidas. También se han utilizado en pruebas de muchos resultados importantes en la teoría de la complejidad computacional, como SL = L (Reingold (2008)) y el teorema PCP (Dinur (2007)). En criptografía, los gráficos de expansión se utilizan para construir funciones hash.

En una encuesta de 2006 sobre gráficos de expansión, Hoory, Linial y Wigderson dividieron el estudio de los gráficos de expansión en cuatro categorías: problemas extremos, comportamiento típico, construcciones explícitas y algoritmos. Los problemas extremos se centran en la delimitación de los parámetros de expansión, mientras que los problemas de comportamiento típicos caracterizan cómo se distribuyen los parámetros de expansión en gráficos aleatorios. Las construcciones explícitas se enfocan en construir gráficos que optimicen ciertos parámetros, y las preguntas algorítmicas estudian la evaluación y estimación de parámetros.

Lema de mezcla de expansores

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

Más formalmente, permita que E(S, T) indique el número de bordes 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 remainE(G[Scap T])$

Entonces el lema de mezcla del expansor dice que se cumple la siguiente desigualdad:

${displaystyle left habitE(S,T)-{frac {dcdot Нованыхcdot нельны} {n}justo en la vidaleq lambda {sqrt {cdot {cdot нельных некованый.}$

Muchas propiedades de los gráficos (n, d, λ) son corolarios de los lemas de mezcla de expansión, incluyendo el seguimiento.

• Un conjunto independiente de un gráfico es un subconjunto de vértices sin dos vértices adyacentes. En un ()n, d, λ)-graph, un conjunto independiente tiene tamaño en la mayoría λn.d.
• El número cromático de un gráfico G, χ(G), es el número mínimo de colores necesarios tal que los vértices adyacentes tienen diferentes colores. Hoffman mostró que d.λ ≤ χ(G), mientras que Alon, Krivelevich y Sudakov demostraron que d. 2n.3, entonces

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

• El diámetro de un gráfico 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 mostró que el diámetro de un ()n, d, λ)- El gráfico es lo más

  ${displaystyle leftlceil log {frac {log(d/lambda)}}rightrceil.}$

Muestreo de recorrido del expansor

El límite de Chernoff establece que, al muestrear muchas muestras independientes de variables aleatorias en el rango [−1, 1], con alta probabilidad, el promedio de nuestras muestras está cerca a la expectativa de la variable aleatoria. El lema de muestreo del recorrido del expansor, debido a Ajtai, Komlós & Szemerédi (1987) y Gillman (1998) afirman que esto también es cierto cuando se muestrea una caminata en un gráfico de expansión. Esto es particularmente útil en la teoría de la desaleatorización, ya que el muestreo de acuerdo con un recorrido de expansión utiliza muchos menos bits aleatorios que el muestreo independiente.

Red de clasificación AKS y mitades aproximadas

Las redes de clasificación toman un conjunto de entradas y realizan una serie de pasos paralelos para clasificar las entradas. Un paso paralelo consiste en realizar cualquier número de comparaciones inconexas y potencialmente intercambiar pares de entradas comparadas. La profundidad de una red está dada por el número de pasos paralelos que toma. Los gráficos de expansión juegan un papel importante en la red de clasificación de AKS, que alcanza la profundidad O(log n). Si bien esta es asintóticamente la profundidad más conocida para una red de clasificación, la dependencia de los expansores hace que el límite constante sea demasiado grande para el uso práctico.

Dentro de la red de clasificación de AKS, los gráficos de expansión se usan para construir ε-halvers de profundidad limitada. Un ε-halver toma como entrada una longitud n permutación de (1, …, n) y divide a la mitad las entradas en dos conjuntos disjuntos A y B tales que para cada entero k ≤ n⁄2 como máximo εk de k las entradas más pequeñas están en B y en la mayoría εk de las k las entradas más grandes están en A. Los conjuntos A y B son una ε-divididas a la mitad.

Después de Ajtai, Komlós & Szemerédi (1983), una profundidad d ε-halver se puede construir de la siguiente manera. Tome un vértice n, grado d< /span> expansor bipartito con partes X y Y de igual tamaño tal que cada subconjunto de vértices de tamaño máximo εn tiene al menos 1 – ε //span>ε vecinos.

Los vértices del gráfico se pueden considerar como registros que contienen entradas y los bordes se pueden considerar como cables que comparan las entradas de dos registros. Al principio, coloque arbitrariamente la mitad de las entradas en X y la mitad de las entradas en Y y descomponer los bordes en d coincidencias perfectas. El objetivo es terminar con X que contiene aproximadamente la mitad más pequeña de las entradas y Y que contiene aproximadamente la mitad más grande de las entradas. Para lograr esto, procese secuencialmente cada coincidencia comparando los registros emparejados por los bordes de esta coincidencia y corrija las entradas que estén fuera de orden. Específicamente, para cada borde de la coincidencia, si la entrada más grande está en el registro en X y la entrada más pequeña está en el registro en Y, luego intercambie las dos entradas para que la más pequeña esté en X y el más grande está en Y. Está claro que este proceso consta de d pasos paralelos.

Después de todas las d rondas, tome A para ser el conjunto de entradas en registros en X y B para ser el conjunto de entradas en registros en Y para obtener un ε-reducción a la mitad. Para ver esto, observe que si un registro u en X y v en Y están conectados por un borde uv luego, después de procesar la coincidencia con este borde, la entrada en u es menor que el de v< /lapso>. Además, esta propiedad se mantiene durante el resto del proceso. Ahora, suponga que para algunos k ≤ n⁄2 que más de εk de las entradas (1, …, k) están en B. Luego, por propiedades de expansión del gráfico, los registros de estas entradas en Y están conectados con al menos 1 – ε/εk se registra en X. En conjunto, esto constituye más de registros k, 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 es. Sin embargo, esto viola la propiedad anterior y, por lo tanto, los conjuntos de salida A y B debe ser una ε-dividida a la mitad.