Regular map (graph theory)

From HandWiki
Short description: Symmetric tessellation of a closed surface


The hexagonal hosohedron, a regular map on the sphere with two vertices, six edges, six faces, and 24 flags.
The regular map {6,3}4,0 on the torus with 16 faces, 32 vertices and 48 edges.

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold (such as a sphere, torus, or real projective plane) into topological disks such that every flag (an incident vertex-edge-face triple) can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

Overview

Regular maps are typically defined and studied in three ways: topologically, group-theoretically, and graph-theoretically.

Topological approach

Topologically, a map is a 2-cell decomposition of a compact connected 2-manifold.[1]

The genus g, of a map M is given by Euler's relation [math]\displaystyle{ \chi (M) = |V| - |E| +|F| }[/math] which is equal to [math]\displaystyle{ 2 -2g }[/math] if the map is orientable, and [math]\displaystyle{ 2 - g }[/math] if the map is non-orientable. It is a crucial fact that there is a finite (non-zero) number of regular maps for every orientable genus except the torus.

Group-theoretical approach

Group-theoretically, the permutation representation of a regular map M is a transitive permutation group C, on a set [math]\displaystyle{ \Omega }[/math] of flags, generated by three fixed-point free involutions r0, r1, r2 satisfying (r0r2)2= I. In this definition the faces are the orbits of F = <r0r1>, edges are the orbits of E = <r0r2>, and vertices are the orbits of V = <r1r2>. More abstractly, the automorphism group of any regular map is the non-degenerate, homomorphic image of a <2,m,n>-triangle group.

Graph-theoretical approach

Graph-theoretically, a map is a cubic graph [math]\displaystyle{ \Gamma }[/math] with edges coloured blue, yellow, red such that: [math]\displaystyle{ \Gamma }[/math] is connected, every vertex is incident to one edge of each colour, and cycles of edges not coloured yellow have length 4. Note that [math]\displaystyle{ \Gamma }[/math] is the flag graph or graph-encoded map (GEM) of the map, defined on the vertex set of flags [math]\displaystyle{ \Omega }[/math] and is not the skeleton G = (V,E) of the map. In general, |[math]\displaystyle{ \Omega }[/math]| = 4|E|.

A map M is regular if Aut(M) acts regularly on the flags. Aut(M) of a regular map is transitive on the vertices, edges, and faces of M. A map M is said to be reflexible iff Aut(M) is regular and contains an automorphism [math]\displaystyle{ \phi }[/math] that fixes both a vertex v and a face f, but reverses the order of the edges. A map which is regular but not reflexible is said to be chiral.

Examples

The hemicube, a regular map.
  • The great dodecahedron is a regular map with pentagonal faces in the orientable surface of genus 4.
  • The hemicube is a regular map of type {4,3} in the projective plane.
  • The hemi-dodecahedron is a regular map produced by pentagonal embedding of the Petersen graph in the projective plane.
  • The p-hosohedron is a regular map of type {2,p}.
  • The Dyck map is a regular map of 12 octagons on a genus-3 surface. Its underlying graph, the Dyck graph, can also form a regular map of 16 hexagons in a torus.

The following is a complete list of regular maps in surfaces of positive Euler characteristic, χ: the sphere and the projective plane.[2]

χ g Schläfli Vert. Edges Faces Group Order Graph Notes
2 0 {p,2} p p 2 C2 × Dihp 4p Cp Undirected 6 cycle.svg Dihedron
2 0 {2,p} 2 p p C2 × Dihp 4p p-fold K2 Hosohedron
2 0 {3,3} 4 6 4 S4 24 K4 3-simplex graph.svg Tetrahedron
2 0 {4,3} 8 12 6 C2 × S4 48 K4 × K2 3-cube column graph.svg Cube
2 0 {3,4} 6 12 8 C2 × S4 48 K2,2,2 Complex tripartite graph octahedron.svg Octahedron
2 0 {5,3} 20 30 12 C2 × A5 120 Dodecahedron H3 projection.svg Dodecahedron
2 0 {3,5} 12 30 20 C2 × A5 120 K6 × K2 Icosahedron A2 projection.svg Icosahedron
1 n1 {2p,2}/2 p p 1 Dih2p 4p Cp Undirected 6 cycle.svg Hemi-dihedron[3]
1 n1 {2,2p}/2 2 p p Dih2p 4p p-fold K2 Hemi-hosohedron[3]
1 n1 {4,3}/2 4 6 3 S4 24 K4 3-simplex graph.svg Hemicube
1 n1 {3,4}/2 3 6 4 S4 24 2-fold K3 Hemioctahedron
1 n1 {5,3}/2 10 15 6 A5 60 Petersen graph Petersen1 tiny.svg Hemidodecahedron
1 n1 {3,5}/2 6 15 10 A5 60 K6 5-simplex graph.svg Hemi-icosahedron

The images below show three of the 20 regular maps in the triple torus, labelled with their Schläfli types.

Toroidal polyhedra

Example visualized as nets
Regular map 4-4 1-0.png
{4,4}1,0
(v:1, e:2, f:1)
Regular map 4-4 1-1.png
{4,4}1,1
(v:2, e:4, f:2)
Regular map 4-4 2-0.png
{4,4}2,0
(v:4, e:8, f:4)
Regular map 4-4 2-1.png
{4,4}2,1
(v:5, e:10, f:5)
Regular map 4-4 2-2.png
{4,4}2,2
(v:8, e:16, f:8)
Regular map 3-6 1-0.png
{3,6}1,0
(v:1, e:3, f:2)
Regular map 3-6 1-1.png
{3,6}1,1
(v:3, e:9, f:6)
Regular map 3-6 2-0.png
{3,6}2,0
(v:4, e:12, f:8)
Regular map 3-6 2-1.png
{3,6}2,1
(v:7, e:21, f:14)
Regular map 3-6 2-2.png
{3,6}2,2
(v:12, e:36, f:24)
Regular map 6-3 1-0.png
{6,3}1,0
(v:2, e:3, f:1)
Regular map 6-3 1-1.png
{6,3}1,1
(v:6, e:9, f:3)
Regular map 6-3 2-0.png
{6,3}2,0
(v:8, e:12, f:4)
Regular map 6-3 2-1.png
{6,3}2,1
(v:14, e:21, f:7)
Regular map 6-3 2-2.png
{6,3}2,2
(v:24, e:36, f:12)

Regular maps exist as torohedral polyhedra as finite portions of Euclidean tilings, wrapped onto the surface of a duocylinder as a flat torus. These are labeled {4,4}b,c for those related to the square tiling, {4,4}.[4] {3,6}b,c are related to the triangular tiling, {3,6}, and {6,3}b,c related to the hexagonal tiling, {6,3}. b and c are whole numbers.[5] There are 2 special cases (b,0) and (b,b) with reflective symmetry, while the general cases exist in chiral pairs (b,c) and (c,b).

Regular maps of the form {4,4}m,0 can be represented as the finite regular skew polyhedron {4,4 | m}, seen as the square faces of a m×m duoprism in 4-dimensions.

Here's an example {4,4}8,0 mapped from a plane as a chessboard to a cylinder section to a torus. The projection from a cylinder to a torus distorts the geometry in 3 dimensions, but can be done without distortion in 4-dimensions.

Torus from rectangle.gif
Regular maps with zero Euler characteristic[6]
χ g Schläfli Vert. Edges Faces Group Order Notes
0 1 {4,4}b,0
n=b2
n 2n n [4,4](b,0) 8n Flat toroidal polyhedra
Same as {4,4 | b}
0 1 {4,4}b,b
n=2b2
n 2n n [4,4](b,b) 8n Flat toroidal polyhedra
Same as rectified {4,4 | b}
0 1 {4,4}b,c
n=b2+c2
n 2n n [4,4]+(b,c) 4n Flat chiral toroidal polyhedra
0 1 {3,6}b,0
t=b2
t 3t 2t [3,6](b,0) 12t Flat toroidal polyhedra
0 1 {3,6}b,b
t=3b2
t 3t 2t [3,6](b,b) 12t Flat toroidal polyhedra
0 1 {3,6}b,c
t=b2+bc+c2
t 3t 2t [3,6]+(b,c) 6t Flat chiral toroidal polyhedra
0 1 {6,3}b,0
t=b2
2t 3t t [3,6](b,0) 12t Flat toroidal polyhedra
0 1 {6,3}b,b
t=3b2
2t 3t t [3,6](b,b) 12t Flat toroidal polyhedra
0 1 {6,3}b,c
t=b2+bc+c2
2t 3t t [3,6]+(b,c) 6t Flat chiral toroidal polyhedra

In generally regular toroidal polyhedra {p,q}b,c can be defined if either p or q are even, although only euclidean ones above can exist as toroidal polyhedra in 4-dimensions. In {2p,q}, the paths (b,c) can be defined as stepping face-edge-face in straight lines, while the dual {p,2q} forms will see the paths (b,c) as stepping vertex-edge-vertex in straight lines.

Hyperbolic regular maps

Octahedron 4 petrie polygons.png Regular map 6 4-3 pattern.png
The map {6,4}3 can be seen as {6,4}4,0. Following opposite edges will traverse all 4 hexagons in sequence. It exists in the petrial octahedron, {3,4}π with 6 vertices, 12 edges and 4 skew hexagon faces.
Branko Grunbaum identified a double-covered cube {8/2,3}, with 6 octagonal faces, double wrapped, needing 24 edges, and 16 vertices. It can be seen as regular map {8,3}2,0 on a hyperbolic plane with 6 colored octagons.[7]

See also

References

  1. Nedela (2007)
  2. Coxeter & Moser (1980)
  3. 3.0 3.1 Séquin (2013)
  4. Coxeter 1980, 8.3 Maps of type {4,4} on a torus.
  5. Coxeter 1980, 8.4 Maps of type {3,6} or {6,3} on a torus.
  6. Coxeter and Moser, Generators and Relations for Discrete Groups, 1957, Chapter 8, Regular maps, 8.3 Maps of type {4,4} on a torus, 8.4 Maps of type {3,6} or {6,3} on a torus
  7. https://web.archive.org/web/20181126084335/https://sites.math.washington.edu/~grunbaum/Your%20polyhedra-my%20polyhedra.pdf

Bibliography