Rotation map

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001345587815 · captured 1774562261.0 · version history

Cite this page as: encyclopegia.org, “Rotation map”, snapshot enwiki-001345587815. https://encyclopegia.org/a/rotation-map

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.