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

## Definition

[edit]

For a D-regular graph G, the rotation map  R o t G : [ N ] × [ D ] → [ N ] × [ D ] {\displaystyle \mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]} is defined as follows:  R o t G ( v , i ) = ( w , j ) {\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.

## Basic properties

[edit]

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

## Special cases and properties

[edit]

* 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  π {\displaystyle \pi } -consistent if  ∀ v   R o t G ( v , i ) = ( v [ i ] , π ( i ) ) {\displaystyle \forall v\ \mathrm {Rot} _{G}(v,i)=(v[i],\pi (i))} . From the definition, a  π {\displaystyle \pi } -consistent rotation map is consistently labeled.

## See also

[edit]

* Zig-zag product
* Rotation system

## References

[edit]

* 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. ISBN 978-0-7695-0850-4. S2CID 420651.

* Reingold, O (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, S2CID 207168478

* 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, ISBN 978-1595931344, S2CID 17360260

* Alexander, C. (2021), A Note on Consistent Rotation Maps of Graph Cartesian Products, doi:10.13140/RG.2.2.19721.57446

* Alexander, C. (2021), Consistent Rotation Maps Induce a Unitary Shift Operator in Discrete Time Quantum Walks, doi:10.13140/RG.2.2.17614.59201