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 {Rot}}_{G}:[N]\times [D]\rightarrow [N]\times [D]$ is defined as follows: ${\mathrm {Rot}}_{G}(v,i)=(w,j)$ if the ith edge leaving v leads to w, and the jth edge leaving w leads to v.

Basic properties

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

Special cases and properties

A rotation map is consistently labeled if all of 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 rotation map is $\pi$ -consistent if $\forall v\ {\mathrm {Rot}}_{G}(v,i)=(v[i],\pi (i))$ . From the definition, a $\pi$ -consistent rotation map is consistently labeled.

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: 3–13, 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

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: 457, doi:10.1145/1132516.1132583

This article is issued from Wikipedia - version of the 5/2/2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Rotation map

Definition

Basic properties

Special cases and properties

See also

References