nLab
combinatorial map

Contents

Idea

A combinatorial map is a representation of a graph embedded in a surface (i.e., a topological map) as a set and a list of permutations acting on that set, with the property that two combinatorial maps are equivalent up to conjugation if and only if the corresponding graphs are isomorphic by a homeomorphism of the underlying surfaces. The precise formulation depends upon assumptions made about the underlying surface (e.g., whether it is connected and/or oriented) and about the underlying graph (e.g., whether all vertices have a fixed degree), but typically different classes of topological maps can be represented by lists of permutations satisfying different sets of constraints.

Oriented maps and hypermaps

Classical combinatorial maps

The following definition corresponds to the case which is perhaps most well-studied:

Definition

A combinatorial map MM is a set DD (whose elements are called darts) equipped with a triple of permutations (σ,α,ϕ)(\sigma,\alpha,\phi) on DD such that:

  1. the subgroup σ,α,ϕ\langle \sigma,\alpha,\phi\rangle of Aut(D)Aut(D) generated by the permutations acts transitively on DD;

  2. the composition of the permutations is the identity: ϕασ=id\phi\alpha\sigma = id;

  3. α\alpha is a fixed point-free involution.

A homomorphism of combinatorial maps

MMM \to M'

where M=(D,(σ,α,ϕ)),M=(D,(σ,α,ϕ))M = (D,(\sigma,\alpha,\phi)), M' = (D',(\sigma',\alpha',\phi')) is a function h:DDh : D \to D' which commutes with each of the respective permutations,

hσ=σhhα=αhhϕ=ϕh.h\sigma = \sigma'h \qquad h\alpha = \alpha'h \qquad h\phi = \phi' h.

Hence, MM and MM' are isomorphic as maps if and only there is a bijection h:DDh : D \cong D' between their underlying sets of darts, such that the triple of permutations (σ,α,ϕ)(\sigma,\alpha,\phi) is mapped by conjugation along hh to the triple of permutations (σ,α,ϕ)(\sigma',\alpha',\phi').

In the literature, many authors equivalently define a combinatorial map by a pair (σ,α)(\sigma,\alpha) of permutations, since by condition (2) above, the third permutation ϕ\phi can always be recovered uniquely as ϕ=σ 1α 1\phi = \sigma^{-1}\alpha^{-1}.

Representing an embedded graph as a combinatorial map

Let θ\theta be an embedding of a graph GG with nn edges into a surface XX which is compact, connected, oriented, and without boundary (below we will just call these “oriented surfaces” for short). We can associate a combinatorial map to this topological embedding, which is unique up to isomorphism:

  • DD is defined as a set containing 2n2n elements, with a pair of distinct darts e +,e De^+,e^- \in D for each edge eGe \in G. These darts may be visualized as oriented edges, or alternatively as half-edges (splitting each of the original edges in the middle).

  • the collection of edges induces a fixed point-free involution α\alpha on DD, by swapping e +e^+ with e e^- for each edge eGe \in G.

  • suppose darts are visualized as oriented edges: we will say that a dart dd is incident to a vertex xx if xx is the unique vertex located at the source of dd. Then every vertex xGx\in G determines a cyclic ordering of the darts incident to xx, by considering (say) a counterclockwise-oriented loop around θ(x)\theta(x). In this way (which relies on the assumption that XX is oriented), each vertex determines a cycle of the permutation σ\sigma.

  • similarly, we say that a dart dd is incident to a face ff (i.e., a connected component of Xθ(G)X \setminus \theta(G)) if ff is the unique face appearing to the left of dd. Then each face ff determines a cyclic ordering of darts incident to ff (corresponding to a counterclockwise traversal along the perimeter of ff), and we can combine these disjoint cycles into a single permutation ϕ\phi.

  • if we start at any dart dDd \in D, then apply the permutation σ\sigma followed by α\alpha followed followed by ϕ\phi, we always end up back at dd.

Hypermaps and constellations

There are several directions for generalizing the classical definition. A small but useful generalization is to drop the requirement that α\alpha be fixed point free, while keeping the requirement that it be an involution (i.e., that α 2=id\alpha^2 = id). This can be seen as allowing the possibility for the graph to include “dangling edges”. In particular, every α\alpha-orbit has length 2 or 1, with orbits of length 2 representing complete edges and orbits of length 1 representing dangling edges.

As a bigger step, it is possible to drop condition (3) altogether:

Definition

A combinatorial hypermap is a set DD equipped with a triple of permutations (σ,α,ϕ)(\sigma,\alpha,\phi) on DD such that:

  1. the subgroup σ,α,ϕ\langle \sigma,\alpha,\phi\rangle of Aut(D)Aut(D) generated by the permutations acts transitively on DD;

  2. the composition of the permutations is the identity: ϕασ=id\phi\alpha\sigma = id.

A combinatorial hypermap gives a representation of a topological embedding of a hypergraph in a oriented surface, but (as noted by Walsh) this is equivalent to an embedding of an ordinary graph equipped with a 2-coloring of its vertices. (Such a graph is necessarily a bipartite graph.) Then, the permutations σ\sigma and α\alpha represent the cycles around the black and white vertices, respectively, while ϕ\phi as before represents the faces. Any ordinary map with all black vertices can be seen as a hypermap with a white vertex dividing each edge (thinking of darts as half-edges), and from that perspective, the definition of hypermap simply corresponds to lifting the restriction that white vertices have degree 2.

Both of these generalizations of the standard notion of combinatorial map are studied in the literature on so-called dessins d'enfants, sometimes using the following terminology to distinguish the different cases:

  • α\alpha is a fixed point free involution : “clean dessin”

  • α\alpha is an involution : “pre-clean dessin”

  • no conditions on α\alpha (besides (1) and (2) above): “dessin”

Another line of generalization is to consider an arbitrary number of permutations (rather than only three). This more general notion of hypermap is called a “constellation” in Lando & Zvonkin.

Definition

A k-constellation is a set DD equipped with a kk-tuple of permutations α 1,,α k\alpha_1,\dots,\alpha_k on DD such that:

  1. the subgroup α 1,,α k\langle \alpha_1,\dots,\alpha_k\rangle of Aut(D)Aut(D) generated by the permutations acts transitively on DD;

  2. the composition of the permutations is the identity: α kα 1=id\alpha_k\dots\alpha_1 = id.

Fixed vertex/edge/face degrees

If one adds, say, the condition that

  • σ 3=id\sigma^3 = id and σ\sigma has no fixed points

to the definition of combinatorial map, then the resulting class of permutations represent embeddings of trivalent graphs, i.e., where every vertex has degree 3. Dually, placing the condition that

  • ϕ 3=id\phi^3 = id and ϕ\phi has no fixed points

gives a way of representing arbitrary triangulations of oriented surfaces. Analogous to what we saw above in the case of the edge involution α\alpha, dropping the condition that σ\sigma or ϕ\phi be fixed point free also allows for the possibility of degenerate vertices/faces of degree 1.

More generally, we can say that a map has type (m,n)(m,n) if the permutations σ\sigma and ϕ\phi have order?s mm and nn respectively (allowing for the possibility that m=m = \infty or n=n = \infty in the case where the set of darts is infinite). This algebraic condition translates to the geometric condition that mm is the least common multiple of the degrees of the vertices of the map, and nn is the least common multiple of the degrees of the faces.

Realizing a combinatorial map as a graph embedded in a Riemann surface

Conversely, any combinatorial map M=(D,(σ,α,ϕ))M = (D,(\sigma,\alpha,\phi)) can be realized as a graph embedded in a surface, in other words as a topological map. The first explicit algorithm for computing such an embedding was given by Edmonds 1960.

The underlying graph G(M)G(M) of MM is easy to describe using the “Serre” definition of a graph (as explained here?) G(M)=(H,V,i,s)G(M) = (H,V,i,s). The set of half-edges HH and the involution ii are just DD and α\alpha, respectively, while the set of vertices VV is the set of σ\sigma-orbits, and the function s:HVs : H \to V sends any dart to its orbit under σ\sigma.

Some more work is required in order to define a surface XX and an embedding of G(M)G(M) into XX. Jones and Singerman 1978 actually proved a stronger result than Edmonds’ algorithm, showing that any combinatorial map (of finite type (m,n)(m,n)) can be realized as a graph embedded in a Riemann surface. As a corollary, this implies that any topological map (on a compact oriented surface without boundary) is isomorphic to some canonical map on a Riemann surface.

Genus of a combinatorial map

The genus gg of a combinatorial map M=(σ,α,ϕ)M = (\sigma,\alpha,\phi) can be defined directly using the Euler-Poincaré formula,

χ(M)=c(σ)c(α)+c(ϕ)=22g\chi(M) = c(\sigma) - c(\alpha) + c(\phi) = 2-2g

where c(π)c(\pi) counts the number of cycles in the cyclic decomposition? of π\pi (i.e., the number of π\pi-orbits). This definition of genus agrees with the genus of the underlying surface of the embedded graph associated to MM.

Dual map

Any embedded graph has a dual graph embedded into the same surface, constructed by placing a vertex in the middle of each face, and connecting two vertices whenever the corresponding faces share an edge. This construction is particularly easy to express on combinatorial maps: for any M=(D,(σ,α,ϕ))M = (D,(\sigma,\alpha,\phi)), the corresponding dual map is defined by M *=(D,(ϕ 1,α 1,σ 1))M^* = (D,(\phi^{-1},\alpha^{-1},\sigma^{-1})). This operation is clearly an involution (with fixed points, since some maps are self-dual). Moreover, it extends to an operation on hypermaps.

Equivalence with other families of objects

Tetravalent maps with bicolored faces

To any graph GG embedded in an oriented surface XX, one can associate a tetravalent graph G mG^m embedded in the same surface XX by the following construction:

  • one vertex v eG mv_e \in G^m for every edge eGe \in G;

  • one edge v e 1v e 2G mv_{e_1} \sim v_{e_2} \in G^m for every ordered pair of edges e 1,e 2Ge_1,e_2 \in G which occur consecutively along the same face in θ(G)\theta(G).

In graph theory, this is known as the medial graph construction. As with the dual graph construction, though, note that this is only well-defined as an operation on embedded graphs (i.e., topological maps) rather than on abstract graphs: the same graph can have different medial graphs, depending on how it is embedded into a surface. To avoid confusion, we refer to this as the medial map construction.

Two topological maps M 1M_1 and M 2M_2 have isomorphic medial maps M 1 mM 2 mM_1^m \cong M_2^m if and only if they are either isomorphic M 1M 2M_1 \cong M_2 or dual M 1M 2 *M_1 \cong M_2^*. To distinguish between duals, one can define a 2-coloring of the faces of the medial map as follows: a face of M mM^m is colored in black just in case it contains a vertex of MM, and white otherwise. The construction of the 2-colored medial map thus defines a one-to-one correspondence between general maps and face 2-colored tetravalent maps on oriented surfaces.

Any alternating virtual link (in the sense of virtual knot theory) is naturally represented by a face 2-colored tetravalent map: each ordinary crossing becomes a vertex of degree 4, with faces colored according to the pattern of under/over crossings (virtual crossings appearing in the link diagram disappear when the knot is embedded into the appropriate surface of higher genus). Thus, any alternating virtual link can be encoded by a unique combinatorial map, and vice versa: see Section 4 of Zinn-Justin and Zuber 2004 where they discuss this representation.

The category of oriented maps

In this section we will adopt the more liberal notion of combinatorial map described above, for which the involution α\alpha is allowed to have fixed points corresponding to “dangling” edges. We will also sometimes write map as shorthand for combinatorial map in this more liberal sense.

Definition

The category of combinatorial maps CMCM is defined as follows:

  • objects are pairs of a set DD together with a triple of permutations (σ,α,ϕ)(\sigma,\alpha,\phi) on DD such that σ,α,ρ\langle\sigma,\alpha,\rho\rangle acts transitively on DD and α 2=ϕασ=id\alpha^2 = \phi\alpha\sigma = id.

  • morphisms (D,(σ,α,ϕ))(D,(σ,α,ϕ))(D,(\sigma,\alpha,\phi)) \to (D',(\sigma',\alpha',\phi')) are functions h:DDh : D \to D' such that hσ=σhh\sigma = \sigma' h, hα=αhh\alpha = \alpha' h, and hϕ=ϕhh\phi = \phi' h.

The category CMCM was defined by Jones and Singerman 1978 essentially as above (they call it AMAM for “algebraic maps”). Specifically, Jones and Singerman take this category to include combinatorial maps in which the involution α\alpha may contain fix points.

Proposition

CMCM is a concrete category, with a faithful functor U:CMSetU : CM \to Set which sends any combinatorial map (D,(σ,α,ϕ))(D,(\sigma,\alpha,\phi)) to its underlying set of darts DD, and any homomorphism of maps h:MMh : M \to M' to a function h:DDh : D \to D' between the underlying sets of darts.

Terminal object

We note that the following property of CMCM relies on allowing maps with dangling edges.

Proposition

The set 1={*}1 = \{ * \} equipped with the triple of identity permutations σ=α=ϕ=id 1\sigma = \alpha = \phi = id_1 is a map, and is a terminal object in CMCM.

The oriented cartographic group

(See also article: cartographic group.)

Definition

The oriented cartographic group 𝒞 2 +\mathcal{C}_2^+ is the group generated by three elements ρ 0,ρ 1,ρ 2\rho_0,\rho_1,\rho_2 satisfying the relations ρ 1 2=ρ 0ρ 1ρ 2=1\rho_1^2 = \rho_0\rho_1\rho_2 = 1.

Proposition

The oriented cartographic group is isomorphic to a free product of the integers with the integers modulo 2, 𝒞 2 + 2\mathcal{C}_2^+ \cong \mathbb{Z} \star \mathbb{Z}_2.

Every combinatorial map is a 𝒞 2 +\mathcal{C}_2^+-set, i.e., a set equipped with an action of the oriented cartographic group. In fact, CMCM is just the full subcategory of 𝒞 2 +Set\mathcal{C}_2^+Set consisting of sets equipped with a transitive action of 𝒞 2 +\mathcal{C}_2^+.

Remark

The modular group? PSL 2() 3 2PSL_2(\mathbb{Z}) \cong \mathbb{Z}_3 \star \mathbb{Z}_2 is a subgroup of the oriented cartographic group. Sets equipped with a transitive action of PSL 2()PSL_2(\mathbb{Z}) are the same thing as trivalent combinatorial maps, which represent trivalent graphs (possibly including degeneracies) embedded in oriented surfaces (or dually, triangulations of oriented surfaces).

For any given map MM with underlying set of darts DD we will denote the action of the oriented cartographic group by

* M:D×𝒞 2 +D,*_M : D \times \mathcal{C}_2^+ \to D,

omitting subscripts when clear from context. The fact that 𝒞 2 +\mathcal{C}_2^+ acts transitively on DD corresponds to the topological condition that the graph represented by MM is connected. As we will see, this places strong restrictions on possible morphisms between maps:

Proposition

A morphism h:M 1M 2h : M_1 \to M_2 of combinatorial maps is entirely determined given the image of a single dart h(d 1)D 2h(d_1) \in D_2.

Proof

Let d 1D 1d_1' \in D_1. By assumption of transitivity, there exists a word w𝒞 2 +w \in \mathcal{C}_2^+ such that d 1=d 1* 1wd_1' = d_1 *_1 w. Hence h(d 1)=h(d 1* 1w)=h(d 1)* 2wh(d_1') = h(d_1 *_1 w) = h(d_1) *_2 w.

Proposition

If h:M 1M 2h : M_1 \to M_2 is a morphism of combinatorial maps and D 1D_1 is inhabited, then the underlying function h:D 1D 2h : D_1 \to D_2 is a surjection.

Proof

Let d 2D 2d_2 \in D_2. By assumption that D 1D_1 is inhabited there exists a d 1D 1d_1 \in D_1, and by assumption of transitivity there exists w𝒞 2 +w \in \mathcal{C}_2^+ such that d 2=h(d 1)* 2wd_2 = h(d_1) *_2 w. Since h(d 1)* 2w=h(d 1* 1w)h(d_1) *_2 w = h(d_1 *_1 w), the dart d 1* 1wD 1d_1 *_1 w \in D_1 is in the inverse image of d 2D 2d_2 \in D_2.

Rooted maps

Enumeration of maps is an active branch of combinatorics, going back to the work of W. T. Tutte in the 1960s. One of the difficulties with trying to count (combinatorial or topological) maps directly, though, is that they can have non-trivial symmetries, which would need to be accounted for to avoid double-counting. This is why combinatorists typically begin with the easier problem of counting rooted maps, as suggested in this autobiographical account by Tutte:

Having made no progress with the enumeration of these diagrams [(strict triangulations of the plane)] I bethought myself of Cayley’s work on the enumeration of trees. His first successes had been with the rooted trees, in which one vertex is distinguished as the “root”. Perhaps I should root the strict triangulations in some way and try to enumerate the rooted ones. Eventually I decided that the rooting should consist of the choice of a face, edge and vertex, mutually incident….

I am not sure what I would have replied at this stage if I had been asked why I preferred these rooted triangulations to the unrooted ones…. Later I realized that the distinguishing feature and the great advantage of rooted maps is that they have no symmetry. Automorphisms seem to complicate enumerative problems.

(From Chapter 10 of W. T. Tutte, Graph Theory As I Have Known It, Oxford, 1998.)

For a combinatorial map (D,(σ,α,ϕ))(D,(\sigma,\alpha,\phi)), choosing “a face, edge and vertex, mutually incident” is equivalent to choosing a dart rDr \in D: the root vertex, edge, and face can then be computed as the orbits of rr under the three permutations. Rooted combinatorial maps may be organized into another category:

Definition

The category of rooted combinatorial maps CM CM_\bullet is defined as follows:

  • objects are pairs of a map M=(D,(σ,α,ϕ))M = (D,(\sigma,\alpha,\phi)) together with a distinguished dart rDr \in D called the root.

  • morphisms (M,r)(M,r)(M,r) \to (M',r') are map morphisms h:MMh : M \to M' in CMCM which preserve the root h(r)=rh(r) = r'.

Note that CM CM_\bullet is equivalent to the comma category 1U1 \downarrow U of the singleton set 1 with the forgetful functor U:CMSetU : CM \to Set. Now we have the following basic observations, in line with the above remarks by Tutte:

Proposition

For M=(D,(σ,α,ϕ))M = (D,(\sigma,\alpha,\phi)) a combinatorial map, the automorphism group Aut(M)Aut(M) is by definition the subgroup of permutations on DD which commute with σ\sigma and α\alpha and ϕ\phi, i.e., the centralizer of σ,α,ϕ\langle\sigma,\alpha,\phi\rangle.

Proposition

For (M,r)(M,r) a rooted combinatorial map, the automorphism group Aut(M,r)Aut(M,r) is always trivial. In particular, if h:(M,r)(M,r)h : (M,r) \to (M,r) is an endomorphism of (M,r)(M,r) in the category of rooted maps CM CM_\bullet, then hh must be the identity morphism.

Proof

Let dDd \in D be any dart of MM. Since the action of 𝒞 2 +\mathcal{C}_2^+ is transitive, there is some word w𝒞 2 +w \in \mathcal{C}_2^+ such that d=r*wd = r * w, and therefore h(d)=h(r*w)=h(r)*w=r*w=dh(d) = h(r * w) = h(r) * w = r * w = d.

References

  • J. Edmonds (1960), A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7, 646.

  • A. Jacques (1970), Constellations et graphes topologiques, Colloque Math. Soc. Janos Bolyai, 657-672.

  • W. T. Tutte. What is a map? In New Directions in Graph Theory (ed. F. Harary), Academic Press, New York, 309-325, 1973.

  • W. T. Tutte. Duality and Trinity. In Infinite and Finite Sets (III), Colloq. Math. Soc. Janos Bolyai, vol. 10, 1459-1472, North Holland, Amsterdam, 1975.

  • Gareth A. Jones and David Singerman, Theory of Maps on Orientable Surfaces. Proceedings of the London Mathematical Society, 37:273-307, 1978.

  • Gareth Jones and David Singerman. Maps, hypermaps, and triangle groups. In The Grothendieck Theory of Dessins d’Enfants, L. Schneps (ed.), London Mathematical Society Lecture Note Series 200, Cambridge University Press, 1994.

  • Sergei K. Lando and Alexander K. Zvonkin, Graphs on Surfaces and Their Applications, Springer, 2004.

  • Samuel Vidal, Groupe Modulaire et Cartes Combinatoires. Génération et Comptage. PhD Thesis, Université Lille I, France, July 2010. pdf

  • Alexander K. Zvonkin, Functional Composition is a Generalized Symmetry, Symmetry: Culture and Science Vol. 21, Nos.1-4, 333-368, 2010. (pdf)

  • P. Zinn-Justin and J.-B. Zuber, Matrix Integrals and the Generation and Counting of Virtual Tangles and Links, Journal of Knot Theory and Its Ramifications, 13:03, May 2004. (arXiv)

  • Wikipedia page: Combinatorial map

Last revised on November 30, 2015 at 16:34:49. See the history of this page for a list of all contributions to it.