Rotation map

In Mathematics, a rotation map is a function that represents an undirected edge-labeled graph (where each vertex enumerates its neighbors in an arbitrary, though fixed, way) through a permutation on pairs of vertex name and edge label. Given a vertex $v$ and an edge label $i$, the rotation map of an undirected labeled graph $G$ will return the $i$'th neighbor of $v$ and the edge label that would lead back to $v$. 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.

Definition

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

Basic Properties

Straight from the definition we see that $Rot_{G}$ is a permutation, and moreover $Rot_{G}\circ Rot_{G}$ is the identity map. In addition, the existence of a rotation map for graph $G$ does not imply that the graph is consistently labeled.

Special cases

1. Let $G$ be a $D$-regular undirected labeled graph with a rotation map that holds $\forall v\ Rot_{G}(v,i)=(v[i],i)$ where $v[i]$ denotes the $i$'th neighbor of $v$. In this case each undirected edge shares the same label for both directions, and colors are often used to describe the labels.
2. Let $G$ be a $D$-regular undirected labeled graph for which exists a function $f:[D]\rightarrow [D]$ which holds$\forall v\ Rot_{G}(v,i)=(v[i],f(i))$

See also

• Zig-zag product
• Rotation system

References

• Reingold, O.; Vadhan, S.; Widgerson, A. (2000), "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors", 41st Annual Symposium on Foundations of Computer Science, doi:10.1109/SFCS.2000.892006

• Reingold, O (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291