Gráfico expansor

Gráfico disperso con fuerte conectividad

En teoría de grafos , un grafo expansor es un grafo disperso que tiene fuertes propiedades de conectividad , cuantificadas mediante expansión de vértices , aristas o espectro . Las construcciones expansoras han generado investigaciones en matemáticas puras y aplicadas, con varias aplicaciones en 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 grafo expansor es un multigrafo finito, no dirigido , en el que cada subconjunto de los vértices que no sea "demasiado grande" tiene un límite "grande" . Diferentes formalizaciones de estas nociones dan lugar a diferentes nociones de expansores: expansores de aristas , expansores de vértices y expansores espectrales , como se definen a continuación.

Un grafo desconectado no es un expansor, ya que el límite de un componente conexo está vacío. Todo grafo conexo es un expansor; sin embargo, diferentes grafos conexos tienen diferentes parámetros de expansión. El grafo completo tiene la mejor propiedad de expansión, pero tiene el mayor grado posible . De manera informal, un grafo es un buen expansor si tiene un grado bajo y parámetros de expansión altos.

Expansión de borde

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 puede escribirse 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 es 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 se deben cortar para dividir el grafo en dos. La expansión de aristas normaliza este concepto al dividir 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 grafos completos con el mismo número de vértices n y agregue 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 puede realizarse de manera equivalente sobre 0 ≤ | S | ≤ n ⁄ 2 o sobre cualquier subconjunto no vacío, ya que . 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 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értices

El número isoperimétrico de vértices h _out ( G ) (también expansión o ampliació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értice 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|}},}$

donde es 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 valor real λ ₁ ≥ λ ₂ ≥ … ≥ λ _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 de n -vértices y d -regulares con

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

como un ( n , d , λ) -grafo . El límite dado 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 , o unilateral , con . Esta última es una noción más débil que se aplica también a los 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 }$

Como 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 grafo G . ^[7] ${\displaystyle u\in \mathbb {R} ^{n}}$

Si nos ponemos

${\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 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 2-norma 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 matriz ⁠1/d⁠ A , que es la matriz de transición de Markov del grafo G . Sus valores propios están entre −1 y 1. Para grafos no necesariamente regulares, el espectro de un grafo 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 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 grafo d -regular G ,

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

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

Desigualdades de Cheeger

Cuando G es d -regular, es decir, cada vértice es de grado d , existe una relación entre la constante isoperimétrica h ( G ) y el hueco 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 grafo 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] establece 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 estricto. El límite inferior se logra en el 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 / n ) ≈ (2 / n ) ² = Θ(1/ n ² ) ${\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 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: ^[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 superiormente por la brecha espectral O ( d – λ ₂ ) .

Construcciones

Existen cuatro estrategias generales para construir explícitamente familias de grafos expansores. ^[13] La primera estrategia es algebraica y de teoría de grupos, la segunda estrategia es analítica y utiliza combinatoria aditiva , la tercera estrategia es combinatoria y utiliza el zigzag y productos gráficos relacionados, y la cuarta estrategia se basa en elevaciones. Noga Alon demostró que ciertos grafos construidos a partir de geometrías finitas son los ejemplos más dispersos de grafos altamente expansivos. ^[14]

Margulis–Gabber–Galil

Se conocen construcciones algebraicas basadas en grafos de Cayley para varias variantes de grafos expansores. 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 G _n 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 grafo G _n tiene el segundo mayor valor propio . ${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$

Gráficas de Ramanujan

Por un teorema de Alon y Boppana , todos los grafos 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 , solo hay un número finito de ( n , d , λ) -grafos. Los grafos de Ramanujan son grafos d -regulares para los cuales este límite es estricto, satisfaciendo ^[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 grafos 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 grafos 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 simple de un resultado ligeramente más débil. ^{[22] [23] [24]}

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

Producto Zig-Zag

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

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

En concreto, ^[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}}}.}$

Nótese que la propiedad (1) implica que el producto en zig-zag de dos gráficos expansores también es un gráfico expansor, por lo tanto los productos en zig-zag se pueden usar inductivamente para crear una familia de gráficos expansores.

Intuitivamente, la construcción del producto en zigzag puede pensarse de la siguiente manera. Cada vértice de G se expande hasta convertirse 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 arista k de v . Dos vértices, ( v , k ) y ( w , l ) están conectados si es posible llegar desde ( v , k ) a ( w , l ) a través de la siguiente secuencia de movimientos.

1. Zig - Muévete desde ( v , k ) a ( v , k' ) , usando un borde 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 desde ( w , l' ) a ( w , l ) usando un borde de H . ^[27]

Ascensores

Un r -lift de un grafo se forma reemplazando cada vértice por r vértices, y cada arista por una correspondencia entre los conjuntos correspondientes de vértices. El grafo elevado hereda los valores propios del grafo original, y tiene algunos valores propios adicionales. Bilu y Linial ^{[28] [29]} demostraron que cada grafo d -regular tiene un 2-lift en el que los valores propios adicionales son como máximo 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 , dando así una construcción eficiente de expansores d -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 de Alon-Boppana . Esta conjetura fue probada en el entorno bipartito por Marcus , Spielman y Srivastava , ^{[25] [26]} quienes usaron el método de entrelazado de polinomios. Como resultado, obtuvieron una construcción alternativa de grafos Ramanujan bipartitos . La prueba no constructiva original fue convertida en un algoritmo por Michael B. Cohen. ^[30] Más tarde, el método fue generalizado a r -lifts por Hall, Puder y Sawin. ^[31] ${\displaystyle O({\sqrt {d\log ^{3}d}})}$ ${\displaystyle 2{\sqrt {d-1}}}$

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 ^[32] quien mostró que para un grafo bipartito regular de n vértices elegidos aleatoriamente a la izquierda d , | 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 ^[33] mostraron que para cada 1 > ε > 0 , hay algún c ( ε ) > 0 tal que se cumple lo siguiente: Para un grupo G de orden n , considérese el grafo de Cayley en G con c ( ε ) log ₂ n elementos elegidos aleatoriamente de G . Entonces, en el límite de n llegando al infinito, el grafo resultante es casi seguramente un ε -expansor.

Aplicaciones y propiedades útiles

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

Los grafos expansores han encontrado amplias aplicaciones en la ciencia informática , en el diseño de algoritmos , códigos de corrección de errores , extractores , generadores pseudoaleatorios , redes de ordenació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 grafos expansores se utilizan para construir funciones hash .

En un estudio de grafos expansores de 2006, Hoory, Linial y Wigderson dividieron el estudio de los grafos expansores 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ípico caracterizan cómo se distribuyen los parámetros de expansión en grafos aleatorios . Las construcciones explícitas se centran en la construcción de grafos que optimizan 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 ( n , d , λ) -grafo, 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 aleatorio d -regular. La aproximación es mejor cuanto menor sea λ . En un grafo aleatorio d -regular, 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 .

Más formalmente, 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 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 ( n , d , λ) -grafos son corolarios de los lemas de mezcla de expansores, incluidas las siguientes. ^[1]

• Un conjunto independiente de un grafo es un subconjunto de vértices sin dos vértices adyacentes. En un ( n , d , λ) -grafo, un conjunto independiente tiene un tamaño máximo de λ 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 ) , ^[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 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 ( n , d , λ) -grafo 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, cuando se muestrean muchas muestras independientes de una variable aleatoria en el rango [−1, 1] , con alta probabilidad el promedio de nuestras muestras está cerca de la expectativa de la variable aleatoria. El lema de muestreo del paseo del expansor, debido a Ajtai, Komlós y Szemerédi (1987) y Gillman (1998), establece que esto también es cierto cuando se muestrea a partir de un paseo en un grafo expansor. Esto es particularmente útil en la teoría de la desaleatorización , ya que el muestreo según un paseo del expansor utiliza muchos menos bits aleatorios que el muestreo independiente.

Red de clasificación AKS y reductores de mitades aproximados

Las redes de ordenamiento 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 realiza. Los gráficos expansores juegan un papel importante en la red de ordenamiento AKS, que alcanza una profundidad O (log n ) . Si bien esta es asintóticamente la profundidad más conocida para una red de ordenamiento, la dependencia de los expansores hace que el límite constante sea demasiado grande para su uso práctico.

Dentro de la red de ordenamiento AKS, se utilizan grafos expansores para construir ε -halvers de profundidad acotada. Un ε -halvers 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 de manera 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 un ε -halving.

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

Los vértices del grafo pueden considerarse como registros que contienen entradas y los bordes pueden considerarse 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 emparejamientos perfectos. El objetivo es terminar con X que contenga aproximadamente la mitad más pequeña de las entradas e Y que contenga aproximadamente la mitad más grande de las entradas. Para lograr esto, procese secuencialmente cada emparejamiento comparando los registros emparejados por los bordes de este emparejamiento y corrija cualquier entrada que esté fuera de orden. Específicamente, para cada borde del emparejamiento, 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 esté en Y . Está claro 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 reducción a la mitad de ε . Para ver esto, note 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 sigue siendo verdadera durante el resto del proceso. Ahora, suponga 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 – ε/mi⁠ 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 ε -halving.

Véase 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. Véase la 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. Discrete Math., vol. 72, págs. 15-19, 1988.
7. Esta definición de la brecha espectral es de la Sección 2.3 en Hoory, Linial y 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 grafos. J. Combin. Theory Ser. B, 47(3):274–291, 1989.
12. Véase el teorema 1 y la pág. 156, l. 1 en Bobkov, Houdré y Tetali (2000). Nótese que λ ₂ corresponde allí a 2( d − λ ₂ ) del artículo actual (véase la pág. 153, l. 5).
13. Véase, por ejemplo, Yehudayoff (2012)
14. Alon, Noga (1986). "Valores propios, expansores geométricos, ordenamiento en rondas y teoría de Ramsey". Combinatorica . 6 (3): 207–219. CiteSeerX  10.1.1.300.5945 . doi :10.1007/BF02579382. S2CID  8666466.
15. Véase, por ejemplo, la pág. 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". Combinatorica . 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). "Expansión de grafos aleatorios: Nuevas pruebas, nuevos resultados". Inventiones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Código Bibliográfico :2015InMat.201..845P. doi :10.1007/s00222-014-0560-x. S2CID  253743928.
23. Puder, Doron (2015). "Expansión de grafos aleatorios: nuevas pruebas, nuevos resultados". Inventiones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Código Bibliográfico :2015InMat.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 trazas para grafos 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: grafos Ramanujan bipartitos 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 Ramanujan bipartitos de todos los tamaños (PDF) . Fundamentos de la ciencia de la computación (FOCS), 56.º simposio anual del IEEE de 2015.
27. Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Ondas de entropía, el producto gráfico en zigzag y nuevos expansores y extractores de grado constante". Actas del 41.º Simposio anual sobre fundamentos de la informática . IEEE Comput. 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 expansores mediante 2-lifts y discrepancia vs. brecha espectral". arXiv : math/0312022 .
29. Bilu, Yonatan; Linial, Nathan (2006). "Ascensores, discrepancia y brecha espectral casi óptima". Combinatorica . 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 la informática (FOCS), 57.º simposio anual del IEEE de 2016. arXiv : 1604.03544 . doi :10.1109/FOCS.2016.37.
31. Hall, Chris; Puder, Doron; Sawin, William F. (2018). "Recubrimientos de grafos 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 sobre informática . SIAM. CiteSeerX 10.1.1.393.1430 . 
33. Alon, N.; Roichman, Y. (1994). "Gráficos aleatorios de Cayley y expansores". Estructuras aleatorias y algoritmos . 5 (2). Wiley Online Library: 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. Alon, Noga ; Krivelevich, Michael ; Sudakov, Benny (1999-09-01). "Coloración de gráficos con vecindarios dispersos". Journal of Combinatorial Theory . 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 Americana . 2 (2): 187–196. doi : 10.1090/S0894-0347-1989-0965008-X . ISSN  0894-0347.

Referencias

Libros de texto y encuestas

• Alon, N. ; Spencer, Joel H. (2011). "9.2. Valores propios y expansores". El método probabilístico (3.ª ed.). John Wiley & Sons.
• Chung, Fan RK (1997), Teoría de grafos espectrales , Serie de conferencias regionales de CBMS sobre matemáticas, vol. 92, American Mathematical Society , ISBN 978-0-8218-0315-8
• Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), Teoría elemental de números, teoría de grupos y grafos de Ramanujan , Textos para estudiantes de LMS, vol. 55, Cambridge University Press , ISBN 978-0-521-53143-6
• Hoory, Shlomo; Linial, Nathan ; Wigderson, Avi (2006), "Gráficos expansores y sus aplicaciones" (PDF) , Boletín de la American Mathematical Society , Nueva serie, 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
• Krebs, Mike; Shaheen, Anthony (2011), Familias expansoras 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 ordenamiento O(n log n)", Actas del 15.º Simposio anual de la ACM sobre teoría de la computación , págs. 1–9, doi :10.1145/800061.808726, ISBN 978-0-89791-099-6, Número de identificación del sujeto  15311122
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Simulación determinista en LOGSPACE", Actas del 19.º Simposio anual de la ACM sobre teoría de la computación , ACM, págs. 132-140, doi : 10.1145/28395.28410 , ISBN 978-0-89791-221-1, Número de identificación del sujeto  15323404
• Alon, N.; Capalbo, M. (2002), "Expansores de vecinos únicos explícitos", 43.° Simposio anual IEEE sobre fundamentos de la informática, 2002. Actas , pág. 73, CiteSeerX  10.1.1.103.967 , doi :10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID6364755 ​
• Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ _∞ , isoperimetría de vértice y concentración", Combinatorica , 20 (2): 153–172, doi :10.1007/s004930070018, S2CID  1173532.
• Dinur, Irit (2007), "El teorema PCP por amplificación gap" (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 diferenciales, desigualdad isoperimétrica y transitoriedad de ciertos recorridos aleatorios", Trans. Amer. Math. Soc. , 284 (2): 787–794, doi : 10.2307/1999107 , JSTOR  1999107.
• Gillman, D. (1998), "Un límite de Chernoff para paseos aleatorios en gráficos expansores", SIAM Journal on Computing , 27 (4): 1203–1220, doi :10.1137/S0097539794268765
• Goldreich, Oded (2011), "Datos básicos sobre los grafos expansores", Estudios en 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, pp. 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 logarítmico", Journal of the ACM , 55 (4): 1–24, doi :10.1145/1391289.1391291, S2CID  207168478
• Yehudayoff, Amir (2012), "Demostrar 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 información compleja encontrada", Quanta Magazine (publicado el 13 de agosto de 2018)

Enlaces externos

• Breve introducción en Avisos de la Sociedad Americana de Matemáticas
• Documento introductorio de Michael Nielsen Archivado el 17 de agosto de 2016 en Wayback Machine.
• Notas de clase de un curso sobre expansores (por Nati Linial y Avi Wigderson)
• Notas de clase de un curso sobre expansores (por Prahladh Harsha)
• Definición y aplicación de gap espectral