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