Rotation map

In mathematics, a rotation map is a function that represents an undirected edge-labeled graph, where each vertex enumerates its outgoing neighbors. Rotation maps were first introduced by Reingold, Vadhan and Wigderson (“Entropy waves, the zig-zag graph product, and new constant-degree expanders”, 2002) in order to conveniently define the zig-zag product and prove its properties. Given a vertex ${\displaystyle v}$ and an edge label ${\displaystyle i}$, the rotation map returns the ${\displaystyle i}$'th neighbor of ${\displaystyle v}$ and the edge label that would lead back to ${\displaystyle v}$.

For a D-regular graph G, the rotation map ${\displaystyle \mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]}$ is defined as follows: ${\displaystyle \mathrm {Rot} _{G}(v,i)=(w,j)}$ if the i th edge leaving v leads to w, and the j th edge leaving w leads to v.

From the definition we see that ${\displaystyle \mathrm {Rot} _{G}}$ is a permutation, and moreover ${\displaystyle \mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}}$ is the identity map (${\displaystyle \mathrm {Rot} _{G}}$ is an involution).