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 and an edge label , the rotation map returns the 'th neighbor of and the edge label that would lead back to .
Definition
For a D-regular graph G, the rotation map is defined as follows: 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 is a permutation, and moreover is the identity map ( 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 -consistent if . From the definition, a -consistent rotation map is consistently labeled.
Reingold, O.; Vadhan, S.; Widgerson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. pp. 3–13.
arXiv:math/0406038.
doi:
10.1109/SFCS.2000.892006.
ISBN978-0-7695-0850-4.
S2CID420651.
Reingold, O.; Trevisan, L.; Vadhan, S. (2006), "Pseudorandom walks on regular digraphs and the RL vs. L problem", Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, pp. 457–466,
doi:
10.1145/1132516.1132583,
ISBN978-1595931344,
S2CID17360260