Rotation map

Not to be confused with Rotation (mathematics).

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 $v$ and an edge label $i$, the rotation map returns the $i$'th neighbor of $v$ and the edge label that would lead back to $v$.

Definition

For a D-regular graph G, the rotation map ${\mathrm{R}\mathrm{o}\mathrm{t}}_G:[N]\times [D]\to [N]\times [D]$ is defined as follows: ${\mathrm{R}\mathrm{o}\mathrm{t}}_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.

Basic properties

From the definition we see that ${\mathrm{R}\mathrm{o}\mathrm{t}}_G$ is a permutation, and moreover ${\mathrm{R}\mathrm{o}\mathrm{t}}_G\circ {\mathrm{R}\mathrm{o}\mathrm{t}}_G$ is the identity map (${\mathrm{R}\mathrm{o}\mathrm{t}}_G$ is an involution).

Special cases and properties

• A rotation map is consistently labeled if all the edges leaving each vertex are labeled in such a way that at each vertex, the labels of the incoming edges are all distinct. Every regular graph has some consistent labeling.
• A consistent rotation map can be used to encode a coined discrete time quantum walk on a (regular) graph.
• A rotation map is $\pi$-consistent if $\mathrm{\forall }v{\mathrm{R}\mathrm{o}\mathrm{t}}_G(v,i)=(v[i],\pi (i))$. From the definition, a $\pi$-consistent rotation map is consistently labeled.

See also

• Zig-zag product
• Rotation system