Gráfico de expansión

Gráfico disperso con fuerte conectividad

En teoría de grafos , un gráfico expansor es un gráfico disperso que tiene fuertes propiedades de conectividad , cuantificadas mediante expansión de vértices , aristas o espectrales . Las construcciones expansoras 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 códigos de corrección de errores . ^[1]

Definiciones

Intuitivamente, un gráfico expansor es un multigrafo finito y no dirigido en el que cada subconjunto de vértices que no es "demasiado grande" tiene un límite "grande" . Diferentes formalizaciones de estas nociones dan lugar a diferentes nociones de expansores: expansores de borde , expansores de vértice y expansores espectrales , como se define 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 conectado es un expansor; sin embargo, diferentes gráficos conectados tienen diferentes parámetros de expansión. La gráfica completa 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 de aristas (también número isoperimétrico o constante de Cheeger ) h ( G ) de un gráfico 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 está sobre todos los conjuntos no vacíos S de como máximo n ⁄ 2 vértices y ∂ S es el límite de arista de S , es decir, el conjunto de aristas con exactamente un punto final 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 gráfico en dos. La expansión de aristas 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. Tome dos gráficos completos con el mismo número de vértices n y agregue n aristas 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 ≤ | S | ≤ n ⁄ 2 o sobre cualquier subconjunto no vacío, desde . No ocurre lo mismo con 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 E(S,{\overline {S}})=E({\overline {S}},S)}$

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

Expansión de vértice

El número isoperimétrico de vértice h _out ( G ) (también expansión o ampliación de vértice ) de un gráfico 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értice h _en ( G ) de un gráfico G se define como

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

donde está el límite interno de S , es decir, el conjunto de vértices en S con al menos un vecino en V ( G ) \ S. ^[3] ${\displaystyle \partial _{\text{in}}(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 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étrico , el teorema espectral implica que A tiene n valores propios de valores 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 bipartito.

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

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

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

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

Debido a que G es regular, la distribución uniforme 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 − λ ₂ y mide la expansión espectral del gráfico G. ^[7] ${\displaystyle u\in \mathbb {R} ^{n}}$

si establecemos

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

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 _{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 se utilizan ampliamente y son más convenientes para expresar algunos resultados. Aquí se considera la matriz1/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 gráficos dirigidos , se consideran los valores singulares de la matriz de adyacenciaA , que son iguales a las raíces de los valores propios de la matriz simétrica A ^T A.

Relaciones entre diferentes propiedades de expansión.

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

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}$

En consecuencia, para gráficos de grados constantes, la expansión de vértices y aristas es cualitativamente la misma.

Desigualdades de Cheeger

Cuando G es d -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 grafos 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 es conexo, entonces λ ₂ < d . Una desigualdad debida a Dodziuk ^[8] e independientemente a Alon y Milman ^[9] afirma que ^[10]

${\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 del 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 / n ) ≈ (2 / n )^2 = Θ(1/ norte ² ) ${\displaystyle \pi }$ ${\displaystyle \pi }$ . ^[1] Un mejor límite se da en ^[11] como

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

Estas desigualdades están estrechamente relacionadas con la desigualdad de Cheeger ligada a 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értice y la brecha espectral: ^[12]

${\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 limitadas arriba por la brecha espectral O ( d – λ ₂ ) .

Construcciones

Hay cuatro estrategias generales para construir explícitamente familias de gráficos de expansión. ^[13] La primera estrategia es algebraica y teórica de grupos, la segunda estrategia es analítica y utiliza combinatoria aditiva , la tercera estrategia es combinatoria y utiliza el zig-zag y productos gráficos relacionados, y la cuarta estrategia se basa en ascensores. Noga Alon demostró que ciertos gráficos construidos a partir de geometrías finitas son los ejemplos más escasos de gráficos altamente expansivos. ^[14]

Margulis-Gabber-Galil

Se conocen construcciones algebraicas basadas en gráficos de Cayley para varias variantes de gráficos de expansión. La siguiente construcción se debe a Margulis y ha sido analizada por Gabber y Galil. ^[15] Para cada número natural n , se considera el grafo Gn con el conjunto de vértices , donde : Para cada vértice , _sus ocho vértices adyacentes son ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$ ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$

${\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 gráfico G _n tiene el segundo valor propio más grande . ${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$

Gráficos de Ramanujan

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

${\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á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 explícitamente los gráficos de Ramanujan. ^[18]

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

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

En 2003, Joel Friedman demostró la conjetura y especificó lo que se entiende por "la mayoría de los gráficos d -regulares" al mostrar que los gráficos d -regulares aleatorios tienen para cada ε > 0 con probabilidad 1 – O ( n ^-τ ) , donde ^{[20 ] [21]} ${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$

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

Puder dio una prueba más sencilla de un resultado ligeramente más débil. ^{[22] [23] [24]}

Marcus , Spielman y Srivastava , ^{[25] [26]} dieron una construcción de gráficos bipartitos de Ramanujan basados ​​en ascensores.

Producto en zig-zag

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

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

Específicamente, ^[27]

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

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

Intuitivamente, la construcción del producto en zig-zag se puede pensar de la siguiente manera. Cada vértice de G se expande hasta formar una "nube" de m vértices, cada uno asociado a un borde diferente conectado 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 se refiere al k ésimo borde de v . Dos vértices, ( v , k ) y ( w , l ) están conectados si es posible pasar de ( v , k ) a ( w , l ) mediante la siguiente secuencia de movimientos.

1. Zig : muévete 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 , l' ) .
3. Zag : muévete de ( w , l ' ) a ( w , l ) usando un borde de H. ^[27]

Ascensores

Una elevación r de un gráfico se forma reemplazando cada vértice por r vértices y cada arista por una coincidencia entre los conjuntos de vértices correspondientes. El gráfico elevado hereda los valores propios del gráfico original y tiene algunos valores propios adicionales. Bilu y Linial ^{[28] [29]} demostraron que cada gráfico d -regular tiene una elevación de 2 en la que los valores propios adicionales tienen como máximo magnitud. También demostraron que si el gráfico inicial es un expansor suficientemente bueno, entonces se puede encontrar un buen 2-lift en tiempo polinomial , dando así una construcción eficiente de d -expansores regulares para cada d . ${\displaystyle r}$ ${\displaystyle O({\sqrt {d\log ^{3}d}})}$

Bilu y Linial conjeturaron que el límite se puede mejorar a , lo que sería óptimo debido al límite Alon-Boppana . Esta conjetura fue probada en el escenario bipartito por Marcus , Spielman y Srivastava , ^{[25] [26]} quienes utilizaron el método de entrelazado de polinomios. Como resultado, obtuvieron una construcción alternativa de gráficos bipartitos de Ramanujan . Michael B. Cohen convirtió la prueba no constructiva original en un algoritmo. ^[30] Posteriormente , Hall, Puder y Sawin generalizaron el método a r -ascensores. ^[31] ${\displaystyle O({\sqrt {d\log ^{3}d}})}$ ${\displaystyle 2{\sqrt {d-1}}}$

Construcciones aleatorias

Existen muchos resultados que muestran la existencia de gráficas con buenas propiedades de expansión mediante argumentos probabilísticos. De hecho, la existencia de expansores fue probada por primera vez por Pinsker ^[32] , quien demostró que para un n vértice elegido aleatoriamente, d gráfico bipartito regular izquierdo , | norte ( 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 es decir O ( d ^-4 ) . Alon y Roichman ^[33] demostraron que por cada 1 > ε > 0 , hay algún c ( ε ) > 0 tal que se cumple lo siguiente: Para un grupo G de orden n , considere el gráfico de Cayley sobre G con c ( ε ) log ₂ n elementos elegidos aleatoriamente de G . Entonces, en el límite de que n llegue al infinito, la gráfica resultante es casi con seguridad un ε -expansor.

Aplicaciones y propiedades útiles.

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

Los gráficos expansores 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 y Szemerédi (1983)) y redes informáticas robustas . 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 un estudio 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 centran en la construcción de gráficos que optimizan ciertos parámetros, y las preguntas algorítmicas estudian la evaluación y estimación de parámetros.

Lema de mezcla del expansor

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

Más formalmente, sea E ( S , T ) el número de aristas entre S y T . Si los dos conjuntos no son disjuntos, los bordes 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 del expansor 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 gráficos ( n , d , λ) son corolarios de los lemas de mezcla del expansor, incluidos los siguientes. ^[1]

• Un conjunto independiente de un gráfico es un subconjunto de vértices sin dos vértices adyacentes. En un gráfico ( n , d , λ ) , un conjunto independiente tiene un tamaño como máximo λ n ⁄ d .
• El número cromático de un gráfico 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 ) , ^[34] mientras que Alon, Krivelevich y Sudakov demostraron que si d < 2 n ⁄ 3 , entonces ^[35]

  ${\displaystyle \chi (G)\leq O\left({\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 demostró que el diámetro de un gráfico ( n , d , λ) es como máximo ^[36]

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

Muestreo de caminata con expansor

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

Red de clasificación de AKS y mitades aproximadas

Las redes de clasificación toman un conjunto de entradas y realizan una serie de pasos paralelos para ordenar las entradas. Un paso paralelo consiste en realizar cualquier número de comparaciones disjuntas 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 desempeñan un papel importante en la red de clasificación de AKS, que alcanza una profundidad O (log n ) . Si bien esta es asintóticamente la profundidad más conocida para una red de clasificación, la dependencia de expansores hace que el límite constante sea demasiado grande para un uso práctico.

Dentro de la red de clasificación AKS, los gráficos de expansión se utilizan para construir mitades ε de profundidad acotada . Un ε -halver toma como entrada una permutación de longitud 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 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 son una ε -reducir a la mitad.

Siguiendo a Ajtai, Komlós y Szemerédi (1983), se puede construir una profundidad d ε -halver de la siguiente manera. Tome un expansor bipartito de n vértices, 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 menos1 – ε/εvecinos.

Los vértices del gráfico se pueden considerar como registros que contienen entradas y los bordes 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 descomponga los bordes en d coincidencias perfectas. El objetivo es terminar con X que contenga aproximadamente la mitad más pequeña de las entradas y que Y contenga 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 cualquier entrada que esté desordenada. 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 , entonces intercambie las dos entradas para que la más pequeña esté en X y la más grande en Y. . Está claro que este proceso consta de 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 reducción a la mitad de ε . Para ver esto, observe que si un registro u en X y v en Y están conectados por un borde uv , luego de procesar la coincidencia con este borde, la entrada en u es menor que la de v . Además, esta propiedad sigue siendo válida durante el resto del proceso. Ahora, supongamos que para algo k ≤ n ⁄ 2 , más de εk de las entradas (1,…, k ) están en B. Luego, por las propiedades de expansión del gráfico, los registros de estas entradas en Y están conectados con al menos1 – ε/εk se registra 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 de modo 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 reducirse a la mitad .

Ver también

• Conectividad algebraica
• Producto en zigzag
• Aproximación superfuerte
• Teoría de grafos espectrales

Notas

1. Hoory, Linial y Wigderson (2006)
2. Definición 2.1 en Hoory, Linial y Wigderson (2006)
3. Bobkov, Houdré y Tetali (2000)
4. Alon y Capalbo (2002)
5. cf. Sección 2.3 en Hoory, Linial y Wigderson (2006)
6. N. Alon y FRK Chung, Construcción explícita de redes tolerantes de tamaño lineal. Matemáticas discretas, vol. 72, págs. 15-19, 1988.
7. Esta definición de brecha espectral proviene de la Sección 2.3 de Hoory, Linial & Wigderson (2006)
8. Dodziuk 1984.
9. Alon y Spencer 2011.
10. Teorema 2.4 en Hoory, Linial y Wigderson (2006)
11. B. Mohar. Números isoperimétricos de gráficas. J. Combinar. Teoría Ser. B, 47(3):274–291, 1989.
12. Véase el teorema 1 y p.156, l.1 en Bobkov, Houdré & Tetali (2000). Tenga en cuenta que λ ₂ corresponde a 2( d − λ ₂ ) del artículo actual (ver p.153, l.5)
13. ver, por ejemplo, Yehudayoff (2012)
14. Alon, Noga (1986). "Valores propios, expansores geométricos, clasificación por rondas y teoría de Ramsey". Combinatoria . 6 (3): 207–219. CiteSeerX  10.1.1.300.5945 . doi :10.1007/BF02579382. S2CID  8666466.
15. ver, por ejemplo, p.9 de Goldreich (2011)
16. Teorema 2.7 de Hoory, Linial y Wigderson (2006)
17. Definición 5.11 de Hoory, Linial y Wigderson (2006)
18. Teorema 5.12 de Hoory, Linial y Wigderson (2006)
19. Alon, Noga (1 de junio de 1986). "Valores propios y expansores". Combinatoria . 6 (2): 83–96. doi :10.1007/BF02579166. ISSN  1439-6912. S2CID  41083612.
20. Friedman, Joel (5 de mayo de 2004). "Una prueba de la segunda conjetura del valor propio de Alon y problemas relacionados". arXiv : cs/0405020 .
21. Teorema 7.10 de Hoory, Linial y Wigderson (2006)
22. Puder, Doron (21 de agosto de 2015). "Ampliación de gráficos aleatorios: nuevas pruebas, nuevos resultados". Invenciones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Código Bib : 2015 InMat.201..845P. doi :10.1007/s00222-014-0560-x. S2CID  253743928.
23. Puder, Doron (2015). "Ampliación de gráficos aleatorios: nuevas pruebas, nuevos resultados". Invenciones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Código Bib : 2015 InMat.201..845P. doi :10.1007/s00222-014-0560-x. ISSN  0020-9910. S2CID  16411939.
24. Friedman, Joel; Puder, Doron (2023). "Una nota sobre el método de seguimiento para gráficos regulares aleatorios". Revista Israelí de Matemáticas . 256 : 269–282. arXiv : 2006.13605 . doi :10.1007/s11856-023-2497-5. S2CID  220042379.
25. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2013). Familias entrelazadas I: gráficos bipartitos de Ramanujan de todos los grados (PDF) . Fundamentos de la informática (FOCS), 54º Simposio anual del IEEE de 2013.
26. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2015). Familias entrelazadas IV: gráficos bipartitos de Ramanujan de todos los tamaños (PDF) . Fundamentos de las Ciencias de la Computación (FOCS), 56º Simposio Anual del IEEE 2015.
27. Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Ondas de entropía, el producto del gráfico en zig-zag y nuevos expansores y extractores de grado constante". Actas del 41º Simposio Anual sobre Fundamentos de la Informática . Computación IEEE. Soc. págs. 3-13. doi :10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID  420651.
28. Bilu, Yonatan; Linial, Nathan (8 de abril de 2004). "Construcción de gráficos de expansión mediante 2 elevaciones y discrepancia versus brecha espectral". arXiv : matemáticas/0312022 .
29. Bilu, Yonatan; Linial, Nathan (2006). "Ascensores, discrepancia y brecha espectral casi óptima". Combinatoria . 26 (5): 495–519. doi :10.1007/s00493-006-0029-7. ISSN  0209-9683. S2CID  14422668.
30. Michael B. Cohen (2016). Gráficos de Ramanujan en tiempo polinomial . Fundamentos de las Ciencias de la Computación (FOCS), 57º Simposio Anual del IEEE de 2016. arXiv : 1604.03544 . doi :10.1109/FOCS.2016.37.
31. Salón, Chris; Puder, Doron; Sawin, William F. (2018). "Revestimientos de gráficos de Ramanujan". Avances en Matemáticas . 323 : 367–410. arXiv : 1506.02335 . doi : 10.1016/j.aim.2017.10.042.
32. Pinkser, M. (1973). "Sobre la complejidad de un concentrador". Revista SIAM de Computación . SIAM. CiteSeerX 10.1.1.393.1430 . 
33. Alon, N.; Roichman, Y. (1994). "Gráficos y expansores aleatorios de Cayley". Estructuras aleatorias y algoritmos . Biblioteca en línea de Wiley. 5 (2): 271–284. doi :10.1002/rsa.3240050203.
34. Hoffman, AJ; Howes, Leonard (1970). "Sobre valores propios y coloraciones de gráficos, Ii". Anales de la Academia de Ciencias de Nueva York . 175 (1): 238–242. Código bibliográfico : 1970NYASA.175..238H. doi :10.1111/j.1749-6632.1970.tb56474.x. ISSN  1749-6632. S2CID  85243045.
35. Alón, Noga ; Krivelevich, Michael ; Sudakov, Benny (1 de septiembre de 1999). "Colorear gráficos con barrios dispersos". Revista de teoría combinatoria . Serie B. 77 (1): 73–82. doi : 10.1006/jctb.1999.1910 . ISSN  0095-8956.
36. Chung, FRK (1989). "Diámetros y valores propios". Revista de la Sociedad Matemática Estadounidense . 2 (2): 187–196. doi : 10.1090/S0894-0347-1989-0965008-X . ISSN  0894-0347.

Referencias

Libros de texto y encuestas.

• Alón, N .; Spencer, Joel H. (2011). "9.2. Valores propios y expansores". El método probabilístico (3ª ed.). John Wiley e hijos.
• Chung, Fan RK (1997), Teoría de grafos espectrales , Serie de conferencias regionales de matemáticas CBMS, vol. 92, Sociedad Matemática Estadounidense , ISBN 978-0-8218-0315-8
• Davidoff, Guiliana; Sarnak, Pedro; Valette, Alain (2003), Teoría elemental de números, teoría de grupos y gráficos de Ramanujan , textos para estudiantes de LMS, vol. 55, Prensa de la Universidad de Cambridge , ISBN 978-0-521-53143-6
• Hoory, Shlomo; Linial, Nathan ; Wigderson, Avi (2006), "Gráficos de expansión y sus aplicaciones" (PDF) , Boletín de la Sociedad Estadounidense de Matemáticas , Nueva serie, 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
• Krebs, Mike; Shaheen, Anthony (2011), Familias de expansores y gráficos de Cayley: una guía para principiantes , Oxford University Press, ISBN 978-0-19-976711-3

Artículos de investigación

• Ajtai, M .; Komlós, J .; Szemerédi, E. (1983), "Una red de clasificación O (n log n)", Actas del 15º Simposio anual ACM sobre teoría de la informática , págs. 1 a 9, doi :10.1145/800061.808726, ISBN 978-0-89791-099-6, S2CID  15311122
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Simulación determinista en LOGSPACE", Actas del 19º Simposio anual ACM sobre teoría de la computación , ACM, págs. 132-140, doi : 10.1145/28395.28410 , ISBN 978-0-89791-221-1, S2CID  15323404
• Alón, N.; Capalbo, M. (2002), "Expansores explícitos de vecinos únicos", 43º Simposio anual del IEEE sobre fundamentos de la informática, 2002. Actas , p. 73, CiteSeerX  10.1.1.103.967 , doi :10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID  6364755
• Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ _∞ , isoperimetría y concentración de vértices", Combinatorica , 20 (2): 153–172, doi :10.1007/s004930070018, S2CID  1173532.
• Dinur, Irit (2007), "El teorema PCP por amplificación de brechas" (PDF) , Journal of the ACM , 54 (3): 12–es, CiteSeerX  10.1.1.103.2644 , doi :10.1145/1236457.1236459, S2CID  53244523.
• Dodziuk, Jozef (1984), "Ecuaciones en diferencias, desigualdad isoperimétrica y fugacidad de ciertos paseos aleatorios", Trans. América. Matemáticas. Soc. , 284 (2): 787–794, doi : 10.2307/1999107 , JSTOR  1999107.
• Gillman, D. (1998), "Un Chernoff destinado a paseos aleatorios en gráficos de expansión", SIAM Journal on Computing , 27 (4): 1203–1220, doi :10.1137/S0097539794268765
• Goldreich, Oded (2011), "Datos básicos sobre gráficos de expansión", Estudios de complejidad y criptografía. Miscelánea sobre la interacción entre aleatoriedad y computación (PDF) , Lecture Notes in Computer Science (Vol. 6650), vol. 6650, págs. 451–464, CiteSeerX  10.1.1.231.1388 , doi :10.1007/978-3-642-22670-0_30, ISBN 978-3-642-22669-4
• Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): 1–24, doi :10.1145/1391289.1391291, S2CID  207168478
• Yehudayoff, Amir (2012), "Demostración de la expansión en tres pasos", ACM SIGACT News , 43 (3): 67–84, doi :10.1145/2421096.2421115, S2CID  18098370

Aplicaciones recientes

• Hartnett, Kevin (2018), "Método universal para ordenar la información compleja encontrada", Revista Quanta (publicada el 13 de agosto de 2018)

enlaces externos

• Breve introducción en Avisos de la Sociedad Matemática Estadounidense
• Documento introductorio de Michael Nielsen
• Apuntes de conferencias de un curso sobre expansores (por Nati Linial y Avi Wigderson)
• Apuntes de conferencias de un curso sobre expansores (por Prahladh Harsha)
• Definición y aplicación de brecha espectral.