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 [math]\displaystyle{ v }[/math] and an edge label [math]\displaystyle{ i }[/math], the rotation map returns the [math]\displaystyle{ i }[/math]'th neighbor of [math]\displaystyle{ v }[/math] and the edge label that would lead back to [math]\displaystyle{ v }[/math].
For a D-regular graph G, the rotation map [math]\displaystyle{ \mathrm{Rot}_G : [N] \times [D] \rightarrow [N] \times [D] }[/math] is defined as follows: [math]\displaystyle{ \mathrm{Rot}_G (v,i)=(w,j) }[/math] if the i th edge leaving v leads to w, and the j th edge leaving w leads to v.
From the definition we see that [math]\displaystyle{ \mathrm{Rot}_G }[/math] is a permutation, and moreover [math]\displaystyle{ \mathrm{Rot}_G \circ \mathrm{Rot}_G }[/math] is the identity map ([math]\displaystyle{ \mathrm{Rot}_G }[/math] is an involution).
Original source: https://en.wikipedia.org/wiki/Rotation map.
Read more |