Producto en zigzag

Operación binaria en teoría de grafos

En teoría de grafos , el producto en zigzag de grafos regulares , denotado por , es una operación binaria que toma un grafo grande ( ) y un grafo pequeño ( ) y produce un grafo que hereda aproximadamente el tamaño del grande pero el grado del pequeño. Una propiedad importante del producto en zigzag es que si es un buen expansor , entonces la expansión del grafo resultante es solo ligeramente peor que la expansión de . ${\displaystyle G,H}$ ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$

En términos generales, el producto en zig-zag reemplaza cada vértice de con una copia (nube) de , y conecta los vértices moviéndose un pequeño paso (zig) dentro de una nube, seguido de un gran paso (zag) entre dos nubes y, finalmente, realiza otro pequeño paso dentro de la nube de destino. ${\displaystyle G\circ H}$ ${\displaystyle G}$ ${\displaystyle H}$

El producto en zigzag fue introducido por Reingold, Vadhan y Wigderson (2000). Cuando se introdujo por primera vez, se utilizó para la construcción explícita de expansores y extractores de grado constante. Más tarde, el producto en zigzag se utilizó en la teoría de la complejidad computacional para demostrar que el espacio logarítmico simétrico y el espacio logarítmico son iguales (Reingold 2008).

Definición

Sea un grafo -regular en con mapa de rotación y sea un grafo -regular en con mapa de rotación . El producto en zigzag se define como el grafo -regular en cuyo mapa de rotación es el siguiente: : ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle [N]}$ ${\displaystyle \mathrm {Rot} _{G}}$ ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle [D]}$ ${\displaystyle \mathrm {Rot} _{H}}$ ${\displaystyle G\circ H}$ ${\displaystyle d^{2}}$ ${\displaystyle [N]\times [D]}$ ${\displaystyle \mathrm {Rot} _{G\circ H}}$
${\displaystyle \mathrm {Rot} _{G\circ H}((v,a),(i,j))}$

1. Dejar . ${\displaystyle (a',i')=\mathrm {Rot} _{H}(a,i)}$
2. Dejar . ${\displaystyle (w,b')=\mathrm {Rot} _{G}(v,a')}$
3. Dejar . ${\displaystyle (b,j')=\mathrm {Rot} _{H}(b',j)}$
4. Producción . ${\displaystyle ((w,b),(j',i'))}$

Propiedades

Reducción del grado

De la definición del producto en zigzag se desprende inmediatamente que transforma un grafo en un nuevo grafo que es -regular. Por lo tanto, si es significativamente mayor que , el producto en zigzag reducirá el grado de . En términos generales, al amplificar cada vértice de en una nube del tamaño del producto, de hecho, se dividen las aristas de cada vértice original entre los vértices de la nube que lo reemplazan. ${\displaystyle G}$ ${\displaystyle d^{2}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$

Preservación de la brecha espectral

La expansión de un grafo se puede medir por su brecha espectral , y una propiedad importante del producto en zigzag es la preservación de la brecha espectral. Es decir, si es un expansor “suficientemente bueno” (tiene una brecha espectral grande), entonces la expansión del producto en zigzag es cercana a la expansión original de . ${\displaystyle H}$ ${\displaystyle G}$

Formalmente: Defina un -grafo como cualquier grafo -regular en vértices, cuyo segundo valor propio más grande (del paseo aleatorio asociado) tiene un valor absoluto como máximo . ${\displaystyle (N,D,\lambda )}$ ${\displaystyle D}$ ${\displaystyle N}$ ${\displaystyle \lambda }$

Sea un -grafo y sea un -grafo, entonces es un -grafo, donde . ${\displaystyle G_{1}}$ ${\displaystyle (N_{1},D_{1},\lambda _{1})}$ ${\displaystyle G_{2}}$ ${\displaystyle (D_{1},D_{2},\lambda _{2})}$ ${\displaystyle G_{1}\circ G_{2}}$ ${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$ ${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$

Preservación de la conectividad

El producto en zigzag funciona por separado en cada componente conectado de . ${\displaystyle G\circ H}$ ${\displaystyle G}$

Formalmente hablando, dados dos gráficos: , un gráfico -regular en y , un gráfico -regular en - si es un componente conexo de entonces , donde es el subgráfico de inducido por (es decir, el gráfico en el que contiene todas las aristas entre los vértices en ). ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle [N]}$ ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle [D]}$ ${\displaystyle S\subseteq [N]}$ ${\displaystyle G}$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D}}$ ${\displaystyle G|_{S}}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle S}$

Aplicaciones

Construcción de expansores de grado constante

En 2002, Omer Reingold, Salil Vadhan y Avi Wigderson dieron una construcción combinatoria simple y explícita de grafos expansores de grado constante. La construcción es iterativa y necesita como bloque de construcción básico un único expansor de tamaño constante. En cada iteración se utiliza el producto en zigzag para generar otro grafo cuyo tamaño aumenta pero cuyo grado y expansión permanecen inalterados. Este proceso continúa, produciendo expansores arbitrariamente grandes.

De las propiedades del producto en zigzag mencionadas anteriormente, vemos que el producto de un grafo grande con un grafo pequeño, hereda un tamaño similar al grafo grande, y un grado similar al grafo pequeño, mientras que conserva sus propiedades de expansión de ambos, permitiendo así aumentar el tamaño del expansor sin efectos deletéreos.

Solución del problema de conectividad st no dirigida en el espacio logarítmico

En 2005, Omer Reingold introdujo un algoritmo que resuelve el problema de la conectividad st no dirigida , es decir, el problema de comprobar si existe un camino entre dos vértices dados en un grafo no dirigido, utilizando únicamente el espacio logarítmico. El algoritmo se basa en gran medida en el producto en zigzag.

En términos generales, para resolver el problema de conectividad st no dirigida en el espacio logarítmico, el grafo de entrada se transforma, mediante una combinación de potenciación y producto en zigzag, en un grafo regular de grado constante con un diámetro logarítmico. El producto de potencia aumenta la expansión (y, por lo tanto, reduce el diámetro) al precio de aumentar el grado, y el producto en zigzag se utiliza para reducir el grado mientras se preserva la expansión.

Véase también

• Operaciones gráficas

Referencias

• 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", Proc. 41.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS) , págs. 3–13, arXiv : math/0406038 , doi :10.1109/SFCS.2000.892006.
• Reingold, O (2008), "Conectividad no dirigida en el espacio logarítmico", Journal of the ACM , 55 (4): Artículo 17, 24 páginas, doi :10.1145/1391289.1391291.
• Reingold, O .; Trevisan, L .; Vadhan, S. (2006), "Recorridos pseudoaleatorios en dígrafos regulares y el problema RL vs. L", Proc. 38.° Simposio ACM sobre teoría de la computación (STOC) , págs. 457–466, doi :10.1145/1132516.1132583.