In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a rotation map is a function that represents an undirected edge-
labeled graph
In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.
Formally, given a graph , a vertex labelling is a function of to a set ...
, 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
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, is a binary operation which takes a large graph (G) and a small graph (H) and produces a graph that approximately inherits the size of the large one but the degree o ...
and prove its properties.
Given a vertex
and an edge label
, the rotation map returns the
'th neighbor of
and the edge label that would lead back to
.
Definition
For a ''D''-regular graph ''G'', the rotation map