Gráfico expansor

En combinatoria , un gráfico expansor es un gráfico disperso que tiene fuertes propiedades de conectividad , cuantificadas usando vértice , borde o expansión espectral. Las construcciones expansivas 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 multigraph finito y no dirigido en el que cada subconjunto de vértices que no es "demasiado grande" tiene un límite "grande" . Las diferentes formalizaciones de estas nociones dan lugar a diferentes nociones de expansores: expansores de borde , expansores de vértices 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. El gráfico completo tiene la mejor propiedad de expansión, pero tiene el mayor grado posible. De manera informal, 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|}},}$

donde ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\in V(G)\setminus S\}.}$

En la ecuación, el mínimo es más de todos los conjuntos no vacíos S de en la mayoría de 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 . ^[2]

Expansión de vértices

El número isoperimétrico de vértice (también expansión o aumento de vértice ) de un gráfico G se define como${\displaystyle h_{\text{out}}(G)}$

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

donde es el límite exterior de S , es decir, el conjunto de vértices en con al menos un vecino en S . ^[3] En una variante de esta definición (llamado expansión vecino único ) se sustituye por el conjunto de vértices en V con exactamente un vecino en S . ^[4]${\displaystyle \partial _{\text{out}}(S)}$${\displaystyle V(G)\setminus S}$${\displaystyle \partial _{\text{out}}(S)}$

El número isoperimétrico de vértice de un gráfico G se define como${\displaystyle h_{\text{in}}(G)}$

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

donde es el límite interior de S , es decir, el conjunto de vértices en S con al menos un vecino en . ^[3]${\displaystyle \partial _{\text{in}}(S)}$${\displaystyle V(G)\setminus 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 es el número de aristas entre los vértices i y j . ^[5] Como A es simétrico , el teorema espectral implica que A tiene n valores propios de valor real . Se sabe que todos estos valores propios están en [- d ,${\displaystyle A_{ij}}$${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$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 -vertex, -regular con un gráfico - . El límite dado por un -graph en para es útil en muchos contextos, incluido el lema de mezcla de expansión .${\displaystyle n}$${\displaystyle d}$${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$${\displaystyle (n,d,\lambda )}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda _{i}}$${\displaystyle i\neq 1}$

Debido a que G es regular, la distribución uniforme con por 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${\displaystyle u\in \mathbb {R} ^{n}}$${\displaystyle u_{i}=1/n}$. ^[6]

Si establecemos , 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\{|\lambda _{2}|,|\lambda _{n}|\}}$

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

donde

${\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 indicar algunos resultados. Aquí se tiene en cuenta la matriz , que es la matriz de transición de Markov de la gráfica 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 matriz simétrica A ^T A .${\displaystyle {\tfrac {1}{d}}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 gráfico d -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 son cualitativamente iguales.

Desigualdades de Cheeger

Cuando G es -regular, es decir, cada vértice es de grado , existe una relación entre la constante isoperimétrico 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 λ ₁ = dy el primer valor propio no trivial es λ ₂ . Si G está conectado, entonces λ ₂ < d . Una desigualdad debida a Dodziuk ^[7] e independientemente Alon${\displaystyle d}$${\displaystyle d}$y Milman ^[8] afirma que ^[9]

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

De hecho, esta desigualdad es estrecha. El límite inferior se logra para el hipercubo , donde y , mientras que el límite superior se logra para un ciclo, dónde y . ^[1] Esta desigualdad está estrechamente relacionada con el límite de Cheeger para las cadenas de Markov y puede verse como una versión discreta de la desigualdad de Cheeger en la geometría riemanniana .${\displaystyle Q_{n}}$${\displaystyle h(G)=1}$${\displaystyle d-\lambda =2}$${\displaystyle H(C_{n})=\Theta (1/n)}$${\displaystyle d-\lambda =\Theta (1/n^{2})}$

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

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

Hablando asintóticamente, las cantidades , y están todas limitadas por encima de la brecha espectral .${\displaystyle {\frac {h^{2}}{d}}}$${\displaystyle h_{\text{out}}}$${\displaystyle h_{\text{in}}^{2}}$${\displaystyle O(d-\lambda _{2})}$

Construcciones

Hay tres estrategias generales para construir explícitamente familias de gráficos expansores. ^[11] La primera estrategia es algebraica y teórica de grupo, 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 demostró que ciertos gráficos construidos a partir de geometrías finitas son los ejemplos más escasos de gráficos de gran expansión. ^[12]

Margulis – Gabber – Galil

Las construcciones algebraicas basadas en 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. ^[13] Para cada número natural n , se considera el gráfico 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 lo siguiente es válido:

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

Artículo principal: gráfico de Ramanujan

Por 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. ^[14] Como consecuencia directa, sabemos que para cada fijo y , sólo hay un número finito de gráficos. Los gráficos de Ramanujan son gráficos d -regulares para los que este límite es estrecho y satisfactorio . ^[15] 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.${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle \lambda _{2}}$${\displaystyle d}$${\displaystyle \lambda <2{\sqrt {d-1}}}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}}$${\displaystyle \lambda _{2}}$

Lubotzky , Phillips y Sarnak (1988), Margulis (1988) y Morgenstern (1994) muestran cómo se pueden construir explícitamente los gráficos de Ramanujan. ^[dieciséis]

En 1985, Alon conjeturó que la mayoría de los gráficos regulares en n vértices, para lo suficientemente grandes , son casi Ramanujan. ^[17] Es decir , porque satisfacen${\displaystyle d}$${\displaystyle n}$${\displaystyle \varepsilon >0}$

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

En 2003, Joel Friedman demostró la conjetura y especificó lo que se entiende por " gráficos más -regulares" mostrando que los gráficos aleatorios d -regulares tienen para todos con probabilidad , donde . ^{[18] [19]}${\displaystyle d}$${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$${\displaystyle \varepsilon >0}$${\displaystyle 1-O(n^{\tau })}$${\displaystyle \tau =\lceil ({\sqrt {d-1}}+1)/2\rceil }$

Producto Zig-Zag

Artículo principal: producto en zig-zag

Reingold , Vadham y Wigderson introdujeron el producto en zig-zag en 2003. ^[20] En términos generales, el producto en zig-zag de dos gráficos expansores produce un gráfico con una expansión solo ligeramente peor. Por lo tanto, también se puede utilizar un producto en zig-zag para construir familias de gráficos expansores. Si es un gráfico y es un gráfico, entonces el producto en zig-zag es un gráfico y tiene las siguientes propiedades.${\displaystyle G}$${\displaystyle (n,m,\lambda _{1})}$${\displaystyle H}$${\displaystyle (m,d,\lambda _{2})}$${\displaystyle G\circ H}$${\displaystyle (nm,d^{2},\varphi (\lambda _{1},\lambda _{2},))}$${\displaystyle \varphi }$

1. Si y , entonces ;${\displaystyle \lambda _{1}<1}$${\displaystyle \lambda _{2}<1}$${\displaystyle \varphi (\lambda _{1},\lambda _{2})<1}$
2. ${\displaystyle \varphi (\lambda _{1},\lambda _{2})\leq \lambda _{1}+\lambda _{2}}$.

Específicamente, . ^[20]${\displaystyle f(\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 expansores también es un gráfico expansor, por lo que los productos en zig-zag se pueden usar inductivamente para crear una familia de gráficos expansores.

Intuitivamente, la construcción del producto en zig-zag se puede pensar de la siguiente manera. Cada vértice de se expande a una "nube" de m vértices, cada uno asociado a un borde diferente conectado al vértice. Cada vértice ahora está etiquetado como where se refiere a un vértice original de y se refiere a la arista de . Dos vértices, y están conectados si es posible pasar de a a través de la siguiente secuencia de movimientos.${\displaystyle G}$${\displaystyle (v,k)}$${\displaystyle v}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$${\displaystyle (v,k)}$${\displaystyle (w,l)}$${\displaystyle (v,k)}$${\displaystyle (w,l)}$

1. Zig : muévase de a , usando un borde de .${\displaystyle (v,k)}$${\displaystyle (v,k')}$${\displaystyle H}$
2. Salta a través de las nubes usando el borde hacia adentro para llegar a${\displaystyle k'}$${\displaystyle G}$${\displaystyle (w,l').}$
3. Zag : muévase de a usando un borde de . ^[20]${\displaystyle (w,l')}$${\displaystyle (w,l)}$${\displaystyle H}$

Construcciones aleatorias

Son muchos los 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 ^[21] quien demostró que para un vértice elegido aleatoriamente a la izquierda un gráfico bipartito regular, para todos los subconjuntos de vértices con alta probabilidad, donde es una constante dependiendo de eso . Alon y Roichman ^[22] demostraron que para cada grupo de orden y cada , hay algunos tales que el gráfico de Cayley con generadores es un expansor, es decir, tiene un segundo valor propio menor que , con alta probabilidad.${\displaystyle n}$${\displaystyle d}$${\displaystyle |N(S)|\geq (d-2)|S|}$${\displaystyle |S|\leq c_{d}n}$${\displaystyle c_{d}}$${\displaystyle d}$${\displaystyle O(d^{-4})}$${\displaystyle G}$${\displaystyle n}$${\displaystyle 1>\varepsilon >0}$${\displaystyle c(\varepsilon )>0}$${\displaystyle G}$${\displaystyle c(\varepsilon )\log _{2}n}$${\displaystyle \varepsilon }$${\displaystyle 1-\varepsilon }$

Aplicaciones y propiedades útiles

La motivación original de los expansores es construir redes económicas robustas (teléfono o computadora): un expansor con valencia limitada 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 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 & Szemerédi (1983) ) y redes informáticas robustas . También se han utilizado en demostraciones de muchos resultados importantes en la teoría de la complejidad computacional , como SL  =  L ( Reingold (2008) ) y el teorema de PCP ( Dinur (2007) ). En criptografía, los gráficos de expansión se utilizan para construir funciones hash .

En una encuesta de 2006 de gráficos expansores , Hoory, Linial y Wigderson dividieron el estudio de gráficos 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ípicos caracterizan cómo se distribuyen los parámetros de expansión en gráficos aleatorios. Las construcciones explícitas se enfocan 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 de expansor

Artículo principal: Lema de mezcla de expansor

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

Más formalmente, deje E ( S , T ) denota el número de aristas entre S y T . Si los dos conjuntos no están separados, 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).}$

Luego, 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 las gráficas son corolarios de los lemas de mezcla de expansores, incluidos los siguientes. ^[1]${\displaystyle (n,d,\lambda )}$

• Un conjunto independiente de un gráfico es un subconjunto de vértices sin dos vértices adyacentes. En un gráfico, un conjunto independiente tiene tamaño como máximo .${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda n/d}$
• El número cromático de un gráfico , , es el número mínimo de colores necesarios de tal manera que los vértices adyacentes tienen diferentes colores. Hoffman demostró eso , ^[23] mientras que Alon, Krivelevich y Sudakov demostraron que si , entonces . ^[24]${\displaystyle G}$${\displaystyle \chi (G)}$${\displaystyle d/\lambda \leq \chi (G)}$${\displaystyle d<2n/3}$${\displaystyle \chi (G)\leq O(d/\log(1+d/\lambda ))}$
• 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 es como máximo . ^[25]${\displaystyle (n,d,\lambda )}$${\displaystyle \lceil \log n/\log(d/\lambda )\rceil }$

Muestreo del recorrido del expansor

Artículo principal: Muestreo de recorrido de 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 de la expectativa de la variable aleatoria. El lema de muestreo de caminata expansiva, debido a Ajtai, Komlós & Szemerédi (1987) y Gillman (1998) , establece que esto también es cierto cuando se toma muestras de una caminata en un gráfico expansor. Esto es particularmente útil en la teoría de la desaleatorización , ya que el muestreo de acuerdo con un recorrido del expansor utiliza muchos menos bits aleatorios que el muestreo de forma independiente.

Red de clasificación AKS y mitades aproximadas

Artículo principal: Red de clasificación

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 disjuntas y potencialmente intercambiar pares de entradas comparadas. La profundidad de una red viene 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 logra profundidad . 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 un uso práctico. ${\displaystyle O(\log n)}$

Dentro de la red de clasificación de AKS, los gráficos de expansión se utilizan para construir puntos de profundidad delimitados. Un -halver toma como entrada una permutación de longitud de y divide a la mitad las entradas en dos conjuntos disjuntos y de tal manera que para cada entero, la mayoría de las entradas más pequeñas están adentro y la mayoría de las entradas más grandes están adentro . Los conjuntos y son una mitad. ${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle (1,\ldots ,n)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle k\leq n/2}$${\displaystyle \varepsilon k}$${\displaystyle k}$${\displaystyle B}$${\displaystyle \varepsilon k}$${\displaystyle k}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \varepsilon }$

Siguiendo a Ajtai, Komlós & Szemerédi (1983) , se puede construir una hilera de profundidad de la siguiente manera. Tome un expansor bipartito de vértice, grado con partes y de igual tamaño de modo que cada subconjunto de vértices de tamaño como máximo tenga al menos vecinos. ${\displaystyle d}$ ${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle d}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \varepsilon n}$${\displaystyle {\frac {1-\varepsilon }{\varepsilon }}}$

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 y la mitad de las entradas y descomponga los bordes en combinaciones perfectas. El objetivo es terminar conteniendo aproximadamente la mitad más pequeña de las entradas y conteniendo 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é fuera de orden. Específicamente, para cada borde de la coincidencia, si la entrada más grande está en el registro en y la entrada más pequeña está en el registro en${\displaystyle X}$${\displaystyle Y}$${\displaystyle d}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$, luego intercambie las dos entradas para que la más pequeña esté adentro y la más grande . Está claro que este proceso consta de pasos paralelos.${\displaystyle X}$${\displaystyle Y}$${\displaystyle d}$

Después de todas las rondas, se toma como conjunto de entradas en registros in y como conjunto de entradas en registros in para obtener un -halving. Para ver esto, observe que si un registro de entrada y de entrada están conectados por un borde, luego de que se procesa la coincidencia con este borde, la entrada de entrada es menor que la de . Además, esta propiedad sigue siendo válida durante el resto del proceso. Ahora, suponga para algunos que más de las entradas están en . Luego, por las propiedades de expansión del gráfico, los registros de estas entradas en se conectan con al menos registros en${\displaystyle d}$${\displaystyle A}$${\displaystyle X}$${\displaystyle B}$${\displaystyle Y}$${\displaystyle \varepsilon }$${\displaystyle u}$${\displaystyle X}$${\displaystyle v}$${\displaystyle Y}$${\displaystyle uv}$${\displaystyle u}$${\displaystyle v}$${\displaystyle k\leq n/2}$${\displaystyle \varepsilon k}$${\displaystyle (1,\ldots ,k)}$${\displaystyle B}$${\displaystyle Y}$${\displaystyle {\frac {1-\varepsilon }{\varepsilon }}k}$${\displaystyle X}$. En conjunto, esto constituye más registros por lo que debe haber algún registro en conectado a algún registro de tal manera que la entrada definitiva de que no se encuentra en , mientras que la entrada final es. Sin embargo, esto viola la propiedad anterior y, por lo tanto, la salida establece y debe ser un -halving.${\displaystyle k}$${\displaystyle a}$${\displaystyle X}$${\displaystyle b}$${\displaystyle Y}$${\displaystyle a}$${\displaystyle (1,\ldots ,k)}$${\displaystyle b}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \varepsilon }$

Ver también

• Conectividad algebraica
• Producto en zig-zag
• 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 & Wigderson (2006)
6. Esta definición de la brecha espectral es de la Sección 2.3 en Hoory, Linial & Wigderson (2006)
7. Dodziuk 1984 .
8. Alon y Spencer 2011 .
9. Teorema 2.4 en Hoory, Linial y Wigderson (2006)
10. Ver 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)
11. ver, p. ej., Yehudayoff (2012)
12. Alon, Noga (1986). "Autovalores, expansores geométricos, clasificación en rondas y teoría de ramsey". Combinatorica . 6 (3): 207–219. CiteSeerX  10.1.1.300.5945 . doi : 10.1007 / BF02579382 . S2CID  8666466 .
13. ver, p. ej., p. 9 de Goldreich (2011)
14. Teorema 2.7 de Hoory, Linial y Wigderson (2006)
15. Definición 5.11 de Hoory, Linial y Wigderson (2006)
16. Teorema 5.12 de Hoory, Linial y Wigderson (2006)
17. Alon, Noga (1 de junio de 1986). "Autovalores y expansores" . Combinatorica . 6 (2): 83–96. doi : 10.1007 / BF02579166 . ISSN 1439-6912 . S2CID 41083612 .  
18. Friedman, Joel (5 de mayo de 2004). "Una prueba de la conjetura del segundo valor propio de Alon y problemas relacionados". arXiv : cs / 0405020 .
19. Teorema 7.10 de Hoory, Linial y Wigderson (2006)
20. Reingold, O .; Vadhan, S .; Wigderson, A. (2000). "Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores y extractores de grado constante" . Actas 41º Simposio Anual sobre Fundamentos de la Informática . Computación IEEE. Soc: 3-13. doi : 10.1109 / sfcs.2000.892006 . ISBN 0-7695-0850-2. S2CID  420651 .
21. Pinkser, M. (1973). "Sobre la complejidad de un concentrador" . Revista SIAM de Computación . SIAM. CiteSeerX 10.1.1.393.1430 . 
22. Alon, N .; Roichman, Y. (1994). "Gráficos y expansores aleatorios de Cayley" . Estructuras y algoritmos aleatorios . Biblioteca en línea de Wiley. 5 (2): 271–284. doi : 10.1002 / rsa.3240050203 .
23. 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 .  
24. Alon, 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 . 
25. 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

• Alon, 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 gráficos espectrales , Serie de conferencias regionales de CBMS en Matemáticas, 92 , American Mathematical Society , ISBN 978-0-8218-0315-8
• Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), teoría de números elemental , teoría de grupos y gráficos de Ramanujan , textos de estudiantes de LMS, 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 Sociedad Americana de Matemáticas , Nueva serie, 43 (4): 439–561, doi : 10.1090 / S0273-0979-06-01126-8
• Krebs, Mike; Shaheen, Anthony (2011), Familias expansoras y gráficos 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), "An O (n log n) sorting network", Actas del 15º Simposio Anual de ACM sobre Teoría de la Computación , págs. 1–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 de 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
• Alon, N .; Capalbo, M. (2002), "Expansores explícitos de vecinos únicos", 43º Simposio Anual de IEEE sobre Fundamentos de la Ciencia de la Computación, 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 de PCP por amplificación de brecha" (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 diferencia, desigualdad isoperimétrica y transitoriedad de ciertos paseos aleatorios", Trad. Amer. Matemáticas. Soc. , 284 (2): 787–794, doi : 10.2307 / 1999107 , JSTOR  1999107.
• Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing , 27 (4): 1203–1220, doi : 10.1137 / S0097539794268765
• Goldreich, Oded (2011), "Basic Facts about Expander Graphs" (PDF) , Estudios de complejidad y criptografía , Lecture Notes in Computer Science, 6650 : 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), "Proving expansion in three steps", ACM SIGACT News , 43 (3): 67–84, doi : 10.1145 / 2421096.2421115 , S2CID  18098370

Aplicaciones recientes

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

enlaces externos

• Breve introducción en Notices of the American Mathematical Society
• Documento introductorio de Michael Nielsen
• 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 la brecha espectral