Rotation map explained

Rotation map should not 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

Rot _{G} : [N] x [D] → [N] x [D] is defined as follows: 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.

Basic properties

From the definition we see that

Rot _{G} is a permutation, and moreover Rot _{G} \circ Rot _{G} is the identity map (Rot _{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 \forall v Rot _{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

References

• Book: O. . Reingold. S. . Vadhan. A. . Widgerson. Proceedings 41st Annual Symposium on Foundations of Computer Science. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. 2000. 10.1109/SFCS.2000.892006. 3–13. math/0406038. 978-0-7695-0850-4. 420651.