Producto en zigzag

Operación binaria en teoría de grafos

En teoría de grafos , el producto en zig-zag de gráficas regulares , denotado por , es una operación binaria que toma una gráfica grande ( ) y una gráfica pequeña ( ) y produce una gráfica que hereda aproximadamente el tamaño de la grande pero el grado de el pequeño. Una propiedad importante del producto en zig-zag es que si es un buen expansor , entonces la expansión de la gráfica resultante es sólo 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 moviendo 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 el producto en zig-zag, se utilizó para la construcción explícita de expansores y extractores de grado constante. Posteriormente, el producto en zig-zag 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 gráfico regular con mapa de rotación y sea un gráfico regular con mapa de rotación . El producto en zig-zag se define como el gráfico 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 de la titulación

De la definición del producto en zigzag se desprende inmediatamente que transforma una gráfica en una nueva gráfica 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 en una nube del tamaño del producto, de hecho se dividen los bordes de cada vértice original entre los vértices de la nube que lo reemplaza. ${\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 gráfico se puede medir por su brecha espectral , siendo una propiedad importante del producto en zigzag la preservación de la brecha espectral. Es decir, si es un expansor "suficientemente bueno" (tiene una gran brecha espectral), entonces la expansión del producto en zigzag es cercana a la expansión original de . ${\displaystyle H}$ ${\displaystyle G}$

Formalmente: defina un gráfico como cualquier gráfico 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, luego 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}$

Hablando formalmente, dados dos gráficos: , un gráfico regular en y , un gráfico regular en - si es un componente conectado de entonces , ¿dónde está el subgrafo de inducido por (es decir, el gráfico que contiene todos los bordes intermedios ? 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 gráficos de expansión 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 gráfico cuyo tamaño aumenta pero su grado y expansión permanecen sin cambios. Este proceso continúa y produce expansores arbitrariamente grandes.

De las propiedades del producto en zigzag mencionadas anteriormente, vemos que el producto de un gráfico grande con un gráfico pequeño hereda un tamaño similar al gráfico grande y un grado similar al gráfico pequeño, al tiempo que conserva sus propiedades de expansión de ambos, por lo tanto permitiendo aumentar el tamaño del expansor sin efectos nocivos.

Resolver el problema de conectividad st no dirigido en espacio logarítmico

En 2005, Omer Reingold introdujo un algoritmo que resuelve el problema de conectividad st no dirigido , el problema de probar si existe un camino entre dos vértices dados en un gráfico no dirigido, utilizando sólo 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 gráfico de entrada se transforma, utilizando una combinación de potencia y el producto en zigzag, en un gráfico regular de grado constante con un diámetro logarítmico. El producto de potencia aumenta la expansión (por lo tanto, reduce el diámetro) al precio de aumentar el grado, y el producto en zigzag se utiliza para reducir el grado preservando la expansión.

Ver también

• Operaciones gráficas

Referencias

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