Rotation map
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 .
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 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 \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). 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.
See also
Zig-zag product Rotation system
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1345587815 under CC BY-SA 4.0; modifications have been made.