Combinatorial
maps
Permutations 
Let us denote by 
finite set of elements. Let us call elements of this set
either simply elements or points or corners. Let us denote elements with small
Greek letters. The cardinality ofis
. Let us call permutation on one-one map from to. In permutation 
let us denote target of 
by
. Thus, we may use for permutation following denotations:
We define multiplication of two permutations and 
denoting it 
as permutation on by formula
. Thus we are multiplicating (or are reading multiplication)
from left to right. Since multiplication of two permutations is always a
permutation then all permutations on shape a group with
respect to multiplication operation that is called permutation group and
denoted by 
(or 
). As is well known the permutation group is full (in sense
faithful) representation of symmetry group in general. Then designates symmetry (or permutation) group’s action on and the symmetry group itself. Permutation group’s identity
element is identity permutation, that is denoted by 
or
, which has identity map on, i.e., it leaves all elements of on place. By 
we designate reverse
permutation of: if maps to
, then reverse permutation maps to.
Simplest forms of permutation’s coding are two row matrix coding or
permutation in cyclical coding form, e.g.:
.
Thus, matrix form is simply 
depicted as two row matrix, but cyclical form runs elements according
their cyclical order. How to attain these forms of codings of permutation? It
is shown in the table:
Indeed, starting with 1, first we find
, then after
, and with 
cycle is closed. Then
we take not yet searched element, say, 2 and find that
and so on, until all elements are searched in their cyclical
order in the permutation. Why we get cycles without repetitions and not
something else? This is because the fact that permutation is bijection (one-one
map).
Cyclical form (of coding) of permutation is more convenient in general
use, because we may give only these elements which are moved, but elements that
remain on place may not be specified in the code. For example, permutations 
and 
are identical, in particular if we do not bother about to
indicate that first permutation acts on set of 8 elements. But permutation 
in matrix form we could not have sufficient space on leaf of
paper to depict. [The problem in general is faced in computer programs where
both ways of coding have their advantages and disadvantages and are to be used
alternately where, of course, the cost of operations on both forms is the
determinant of the way of coding. On computer, transform from one code to other
is linear operation. Similarly, multiplication in matrix form is linear
operation and many other operations are linear or near to that. Thus,
permutational calculus, and combinatorial maps’ calculus can be performed in
very powerful fashion.]
It is easy to see that cyclical form of permutation structurally is set
of cyclical lists. This means that by changing cycles in the form or cyclically
changing elements in a cycle does not change the permutation in general. For
example, the permutation in the previous example can be put down in the way 
too.
Transposition is a permutation which changes two
elements in their places but other remains as they are: transposition 
has always cyclical
form 
. Each permutation can
be written in the form of multiplication of transpositions 
. For example the previous permutation can be given as
multiplication of transpositions in the form 
. Performing all multiplications, multiplying from left to
right, we should return to the previous (canonical) cyclical form. Try it! It
is easy to see that this way of presenting of permutation in the form of
multiplication of transpositions is not unique. However, either is even or odd is
invariant of the permutation.
Combinatorial
maps
Let us consider the simplest way of defining of the
combinatorial map when it has graph on surface in the correspondence.
Let us have set with 
elements that are
called corners. On set permutations should
act, and they are the objects we are going to deal with.
Definition 1.Two permutationsand of order are distinct, if 
for each 
.
Permutation is said to be involution if all its
cycles are of order two.
Definition 2. Oriented pair 
of two distinct permutations is called combinatorial map if
the multiplication
is involution.
Combinatorial map defined in this way is called
geometrical combinatorial map.
Let pair be combinatorial map. Multiplication
that is involution is
called edge rotation and is denoted by 
. Thus, consists of distinct transpositions.
Definition 3. Let pair be combinatorial map. is called vertex
rotation and is called face
rotation.
Example 1. Let 
and 
. be combinatorial map
with edge rotation equal to
.
Exercise 1. Try to connect combinatorial map from exercise 1 with the picture of graph in fig. 1. Hint.
Numbers are to be considered as labels of ‘corners’ and cyclical orders of
‘corners’ around vertices and faces are to be considered as permutations. Find vertex, face and edge rotations in the
picture of the corresponding graph.
The
correspondence between combinatorial maps and graphs on surfaces.
Let graph 
be embedded on oriented surface 
. This means that for each vertex 
the edges that are adjacent with this vertex are cyclically
ordered around it, and in the same time the cyclical order of incident faces on
around vertex 
is given too.
Let 
be set of neighbors of vertex . Cyclical order of edges around induces cyclical order in the set .
Let us denote the cyclically ordered sequence of
neighbors of by 
, where is number of neighbors.
Induced cyclical sequence 
, that consists from oriented edges around vertex in the same way
characterizes the embedding of the neighborhood of on the surface . Outgoing (oriented) edges of each vertex form such cyclical
sequence and outgoing (oriented) edges of all vertices form a permutation (because each such
oriented edge is unique). That means that the embedding of the graph on surface
is uniquely determined
by the permutation (=) that acts on set of oriented edges 
. Let us denote this permutation by 
(=). Thereby, the embedding of on can be given or fixed
as 
.
Let us form one more permutation that characterizes
the graph’s embedding on the surface . Let us consider arbitrary face 
with border (as
sequence of vertices) 
, where the face 
is passed round in the
direction opposite to clockwise. Thus, f is oriented anticlockwise and can be
characterizes by cyclical oriented sequence of oriented edges i.e., 
. Cyclical oriented sequences of all faces form induce a
permutation that acts on set of oriented edges . Indeed, if arbitrary oriented edge goes into border of the
face, then only once and only in the border of this face. By the same reason
each oriented edges goes into border at least one face. Let us denote this
permutation with 
. Thus, embedding of on can be given as 
. This is equivalently with the previous way of determining
the embedding of on . Thus, graph may be fixed on either by permutation or . More radical discovery tells us that graph on surface may
be determined without specifying sets 
and 
at all, but specifying
only pair of permutations 
that is isomorphic to
. Let us call this mathematical fact Hefter-Edmonds theorem. It
was contrived by Hefter as early as 1898, but in contemporary form proved by
Combinatorial
maps. Systematic insight.
Let 
be two permutations. Combinatorial map is called geometrical
if 
is involution without
fixed points.
Proposition 1. Geometrical map has even number of
corners.
Proof. If map has odd number of edges then J is involution with odd
number of elements that has at least one fixed element.
Let us call involution 
inner edge rotation
but 
– edge rotation.
We shall see further the difference between both clearer.
Pair of corners 
is called edge if 
. Let us denote this edge by 
.
Proposition 2. If is edge and belongs to 
, then 
belongs to .
Let us prove that 
. From that should follow what is asserted. Indeed:
.
Let us call inner edge, being simply edge. If is edge rotation for a
map, then is inner edge rotation. We have proved that application of
vertex rotation to edge rotation gives inner edge rotation. Symmetric
expression holds too: 
. Indeed:
It is easy to see that following expressions holds
too: 
and 
.
It is
convenient to observe some terminology. Thus we are speaking that 
are acting on set of corners or elements.
This set of elements is divided by
into 
pairs. Let 
be such pair that 
. Provided already belongs to inner edge rotation then there exists a
pair 
that belongs to edge
rotation, that holds 
. It may be very convenient not to consider combinatorial
maps separately with variable inner edge rotations but as classes of maps with
one fixed inner edge rotation . For such fixed map 
has its unique edge
rotation , that holds . Thus, is common for a class,
but is depending from a
map 
. In its turn, it becomes quite clear that map is determined only by one rotation, namely, vertex rotation .
We should keep in mind:
Map’s mirror reflection and dual map.
What looks like combinatorial map’s mirror reflection?
Proposition 1. Map has symmetric
reflection’s map 
in correspondence.
Indeed. Mirror reflected vertex and face rotations
change their directions from, say, clockwise to anticlockwise [for vertex
rotation] and vice versa [for face rotation]. Thus, we could write 
and 
.
Proposition 2. Maps and change their places in mirror reflection in the way 
and 
.
Indeed, from 
follow that 
and 
. [We used the fact that multiplication’s reflected map is
reverse map, i.e., 
]. Thus, in mirror reflection rotations and change as if in their
places.
Trying to define map’s dual map simply as 
we use its geometrical
interpretation. Thus we write 
. What we get for edge rotations? If in rotation 
we change and in their places, then
rotation itself does not change, thus, 
. 
. But maps themselves, namely, dual map and reflected map,
they are different.
Let be universal set of corners and be fixed. We are in
the class of maps, say, 
. Map may be designated with
one letter, namely, . Thus, we have and would like to have
and 
too. But we may take
in our class of maps only those which have the same rotation . Thus is not member of and we are going to
define what could be called reverse map, that is now within . Thus reverse map or 
is defined as 
. It has, of course, 
and
.
Correspondence between permutations’
and combinatorial maps’ classes
Let class 
have all combinatorial
maps with inner edge rotation fixed. Then class’s members may be characterized with pairs 
or 
or, keeping in mind, only with one
permutation, say, that of vertex rotation, , where may be always
calculated using formula 
.
Thus, living within fixed rotation or saying that we live
within , every permutation has its combinatorial map in
correspondence. Identical permutation 
has map 
in correspondence that in its turn has graph with 
isolated edges. Transposition
has map 
and star graph 
in correspondence.
Multiplication of combinatorial maps.
Let us define multiplication of maps in the class . Let us permutation multiplication take as the base
operation. Let us try to define multiplication of maps in the way that class is closed against this
operation. Let 
and 
to class of maps with fixed inner edge rotation , i.e., to class .
Definition. We define multiplication of two maps in
the way:
where 
and 
It is easy to see that map 
belongs to class : 
.
We may write
.
We may write in more symmetric way too:
.
Further, multiplying maps, we may treat maps as
permutations remembering that behind permutations we have maps.
Actually, we may be free in the interchange between
maps and permutations within , because of the one-one correspondence between them. We even
have more. Every theorem that holds for permutations has its meaning in maps’
interpretation too. Thus every permutational theorem has combinatorial map’s
theorem in correspondence.
Further we are not going to use different designators
for multiplication of maps and permutations.
Permutations constitute symmetric group
, which acts on corner set . Group has group 
in correspondence .
Normalized combinatorial maps
Practically working with combinatorial maps with fixed
inner edge rotation it would be convenient
to choose some fixed ‘for all cases of
life’. We have chosen equal with 
, id est, 
inner edge is equal to
. Let us further accept this form of and use in all cases
with excuse in cases when it is necessary.
If is given it is easy to
find : if in element 
has 
in correspondence,
then for corresponding element
is equal to 
, if 
is even, and equal to 
, if is odd. For example, for
given 
let us calculate :, gives 
; cyclically continuing:, 
, gives 
; further , gives 
; 
, gives 
; 
, gives 
; 
, gives;
, 
, gives 
; at last, 
, gives 
and cycle is closed. We
got: 
. Let us show these operations in the table:
It is easy to see in 3-permutation where second row
shows and third row shows :
.
Exercise 1. Find for given 
using the method given
above.
Exercise 2. Find , for given
.
Hint: if cycle ends start new cycle taking not yet
searched element.
Let us calculate edge rotation of normalized map using
formula 
:
Let us calculate edge rotation of normalized map,
namely, using formula and previous method of
calculating in the way [prove that
it is correctly]:
Exercise 3. Calculate edge rotation for maps 
and 
, using the method given above!
Geometrical
interpretation of combinatorial maps.
Combinatorial map may be interpreted as graph on
orientable surface. The fact corresponds to Hefter-Edmonds theorem.
In place to try to prove this theorem we suggest
following construction which shows what is behind this theorem and how
combinatorial maps may be considered as graphs on surfaces.
Constructive
assumption. Using one general method, to arbitrary combinatorial map a graph may
be mapped that is drawn in the plane with edge crossings in general.
Note. Any graph may be drawn in the
plane with edge crossing in general.
Construction.
Let be vertex rotation of
the combinatorial map. Each cycle of length 
let us picture as a
vertex with halfedges, between which
we put numbers of corners clockwise in the order corresponding to this cycle. Arbitrary
inner edge 
of the map 
we picture in the plane followingly: let us find halfedge
that is before corner with number moving clockwise; likewise let us find 
; let us connect halfedges and with a non crossing
curve, but allowing crossings with other similar connections if necessary. Corresponding
edge to this inner edge should be 
, where 
follows anticlockwise 
and 
follows anticlockwise 
in . Iteratively applying this operation, we get map pictured in
the plane in the sense of this construction.
Illustration of connection of inner halfedges and halfedges in the drawing of the map in plane in case of
different vertices.
Illustration of connection of inner halfedges end halfedges in the drawing of the map in plane in case of the same
vertex.