Mapa de rotación

En matemáticas , un mapa de rotación es una función que representa un grafo no dirigido con etiquetas en sus aristas, donde cada vértice enumera sus vecinos salientes. Los mapas de rotación fueron introducidos por primera vez por Reingold, Vadhan y Wigderson (“Ondas de entropía, el producto de grafos en zigzag y nuevos expansores de grado constante”, 2002) para definir convenientemente el producto en zigzag y demostrar sus propiedades. Dado un vértice${\displaystyle v}$y una etiqueta de borde${\displaystyle i}$, el mapa de rotación devuelve el${\displaystyle i}$'el vecino de${\displaystyle v}$y la etiqueta del borde que conduciría de vuelta a${\displaystyle v}$.

Para un grafo D -regular G , el mapa de rotación${\displaystyle \mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]}$se define de la siguiente manera:${\displaystyle \mathrm {Rot} _ {G}(v,i)=(w,j)}$si la i -ésima arista que sale de v conduce a w , y la j -ésima arista que sale de w conduce a v . 

De la definición vemos que${\displaystyle \mathrm {Rot} _ {G}}$es una permutación, y además${\displaystyle \mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}}$es el mapa identidad (${\displaystyle \mathrm {Rot} _ {G}}$es una involución ).

• Un mapa de rotación está etiquetado de forma consistente si todas las aristas que salen de cada vértice están etiquetadas de tal manera que, en cada vértice, las etiquetas de las aristas entrantes son todas distintas. Todo grafo regular tiene algún tipo de etiquetado consistente.
• Se puede utilizar un mapa de rotación consistente para codificar un paseo cuántico de tiempo discreto acuñado en un grafo (regular).
• Un mapa de rotación es${\displaystyle \pi }$-consistente si${\displaystyle \forall v\ \mathrm {Rot} _ {G}(v,i)=(v[i],\pi (i))}$. Según la definición, un${\displaystyle \pi }$-El mapa de rotación consistente está etiquetado de forma consistente.

• Producto en zigzag
• Sistema de rotación