Action graphs and coverings.
An action graph is a combinatorial representation of a group acting on a set. Comparing two group actions by an epimorphism of actions induces a covering projection of the respective graphs. This simple observation generalizes and unifies many well-known results in graph theory, with applications ranging from the theory of maps on surfaces and group presentations to theoretical computer science, among others. Reconstruction of action graphs from smaller ones is considered, some results on lifting and projecting the equivariant group of automorphisms are proved, and a special case of the split-extension structure of lifted groups is studied. Action digraphs in connection with group presentations are also discussed.
Introduction
With a group G acting on a set Z we can naturally associate, relative to a subset
(di)graph called the action (di)graph. Its vertices are the elements
of the set Z, with adjacencies being induced by the action of the elements of S on Z.
The denition adopted here is such that a connected action (di)graph corresponds
to a Schreier coset (di)graph, with \repeated generators" and semiedges allowed.
However, to think of an action (di)graph actually as a Schreier coset (di)graph is
much too rigid in many instances. For similar concepts dealing with (di)graphs and
group actions see [1, 2, 3, 8, 12, 17, 18, 21, 22, 28, 43, 45]. Some of them, although
conceptually dierent, bare the same name [45], and some of them, quite close to
our denition, are referred to by a variety of other names [1, 3]. It seems that
the term action (di)graph should be attributed to T. Parsons [43]. For a computer
implementation of (a variant of) action graphs see [44].
Supported in part by \Ministrstvo za znanost in tehnologijo Slovenije", proj.no. J1-0496-99.
Group actions are compared by morphisms. The starting observation of this
paper is that an epimorphism between two actions invokes a covering projection of
the respective action graphs. Surprisingly enough, this simple result does not seem
to have been explicitly stated so far, although there are many well-known special
cases with numerous applications.
For instance, it is generally known that Schreier coset (di)graphs are actually
covering (di)graphs, and that a Schreier coset (di)graph is regularly covered by its
corresponding Cayley (di)graph. These facts are commonly used as background
results in the theory of group presentations [12, 13, 28, 31, 32, 14, 48, 52], and have
recently been applied in the design and analysis of interconnection networks and
parallel architectures [1, 2, 3, 22], among others. Coverings of Cayley graphs are
frequently employed to construct new graphs with variuos types of symmetry and
other graph-theoretical properties [9, 19, 34, 47] as well as to prove that a subgroup
cannot have genus greater than the group itself [7, 19]. As for the maps on surfaces
[4, 5, 10, 16, 19, 20, 25, 26, 27, 30, 35, 36, 40, 41, 46], one of the many combinatorial
approaches to this topic is by means of a Schreier representation [25, 40]. Such a
representation is actually a certain action graph in disguise, and homomorphisms
of maps correspond to covering projections of the respective action graphs. Some
important basic facts can be elegantly derived along these lines.
We here give a unied approach to all these diverse topics, and in addition, we
derive certain results which appear to be new. Section 2 is preliminary. Action
graphs are introduced formally in Section 3, and covering projections induced by
morphisms of actions in Section 4. Further basic properties of such coverings are
discussed in Sections 5 and 6. In Section 7 we brie
y consider automorphism groups
of action graphs. Section 8 is devoted to lifting and projecting automorphisms, with
focus on the equivariant group. In Section 9 we determine the group of covering
transformations, and apply some results of [35] to obtain conditions for a natural
splitting of a lifted group of map automorphisms (valid also if the map homomorphism
is not valency preserving [35, 36]). In Section 10 we treat action digraphs in
connection with group presentations. The lifting problem along a regular covering
(of graphs as well as of general topological spaces) is reduced to a question about
action digraphs.
Preliminaries: Group actions, Graphs and Coverings
By an ordered pair (Z; G) we denote a group G acting on the right on a nonempty
set Z. (For convenience we omit the dot sign indicating the action.) A morphism
of actions is an ordered pair
function and : G ! G 0 is a homomorphism such that (u
Morphisms are composed on the left. Left actions and their morphisms are dened
similarly. Morphisms of the form (; id) : (Z; are called equivariant,
and morphisms of the form (id; are called invariant. Invariant
epimorphisms formalize the intuitive notion of \groups, acting in the same way on
a given set".
We say that an action ( ~
covers an action (Z; G) whenever there exists
an epimorphism (;
This terminology is justied by the
fact that the cardinality j 1 (z)j depends just on the orbit of G to which z 2 Z
belongs. A covering of actions
can be decomposed into
an equivariant covering
followed by an invariant covering
where the action of ~
G on Z is dened by z  ~
Proposition 2.1 There exists a covering ( ~
of transitive actions if
and only if there exists, for a xed chosen ~ b 2 ~
Z, a group
such that q( ~
Z. The corresponding onto mapping of sets is
then given by  ~ b;b ( ~ b~g) := bq(~g). In particular, two transitive actions are isomorphic
if and only if there exists an isomorphism between the respective groups mapping a
stabilizer onto a stabilizer.
Example 2.2 Let H  H 0  G and K/G. The group G acts by right multiplication
on the set of right cosets HjG. Similarly, the quotient group G=K acts on the
set of right cosets H 0 KjG. There is an obvious covering of actions (HjG;
In particular, the regular action (G; G) r of G on itself by right
multiplication covers any transitive action of G=K.
Example 2.3 There is an equivariant isomorphism representing a transitive action
of a group G as an action on the cosets of a stabilizer. Moreover, all transitive and
faithful quotient actions of G can be treated in a similar fashion.
Indeed, a conjugacy class C of subgroups in G determines the action of G=core(C)
on the cosets of an element of C. This action is transitive and faithful. Conversely,
Q be a group epimorphism and let (Z; Q) be transitive and faithful.
Dene the action (Z; G) such that (id; is an invariant covering,
and let G Q
b be a stabilizer of (Z; G). Let
jG; G) be the
standard representation of (Z; G). Then
jG; Q) is the standard
representation of (Z; Q). It follows that (Z; Q) determines a conjugacy class C Q in
G with core(C Q q. Thus, the isomorphism classes of transitive and faithful
actions of quotient groups of G are in natural correspondence with conjugacy classes
of subgroups in G. Moreover, covering satisfying
is a morphism. That is, such a
covering exists if and only if G Q
b is contained in a conjugate subgroup of G Q 0
b . See
Examples 4.7 and 4.8 for an application.
By Aut(Z; G) we denote the automorphism group of (Z; G). An automorphism
of G is called admissible whenever there exists a bijection  on Z such that
G). The group of admissible automorphisms is denoted by AdmZ G.
By Aut(Z)G we denote the equivariant group of the action, formed by all bijections
on Z for which (; id) 2 Aut(Z; G). If (Z; G) is transitive, then Aut(Z)G can be
computed explicitly relative to a point of reference b 2 Z as
. Also, the left action of Aut(Z)G on Z is
xed-point free, and is transitive if and only G acts with a normal stabilizer. Hence
if G is, in addition, faithful, then Aut(Z)G is regular if and only if G is regular. In
this case, (Z; G) is essentially the right multiplication (G; G) r , whereas (Aut(Z)G ; Z)
is essentially the left multiplication (G; G) l .
A graph is an ordered 4-tuple are disjoint
nonempty sets of darts and vertices, respectively, beg is an onto mapping
which assigns to each dart x its initial vertex beg x, and inv : D ! D is an involution
which interchanges every dart x and its inverse x x. For notational
convenience we use beg and inv just as symbolic names denoting the actual concrete
functions. The terminal vertex end x of a dart x is the initial vertex of x 1 . The
orbits of beg are called edges. An edge is called a semiedge if x
and it is called a link otherwise. Walks are
dened as sequences of darts in the obvious way. By
we denote the set of all walks and the set of all u-based closed walks of a graph X,
respectively. By recursively deleting all consecutive occurrences of a dart and its
inverse in a given walk we obtain its reduction. Two walks with the same reduction
are called homotopic. The naturally induced operation in set of all reduced u-based
closed walks denes the fundamental group  morphism of graphs
. For convenience we write
are the appropriate restrictions. Graph morphisms are composed on the left.
A graph
called a covering projection if, for every
vertex ~
X , the set of darts with ~
u as the initial vertex is bijectively mapped
onto the set of darts with the initial vertex p(~u). The graph X is called the base
graph and ~
X the covering graph. By b we denote the
bre over the vertex u and the dart x of X, respectively. A morphism of covering
projections is an ordered pair (f; ~
f) of graph morphisms f
~
f . An equivalence of covering projections p and
0 of the same base graph is a morphism of the the form (id; ~
f is graph
isomorphism. Equivalence of covering projections dened on the same covering
graph is dened similarly. An automorphism of
is of course a pair of
automorphisms ( ~
f . The automorphism ~
f is called a lift of f ,
and f the projection of ~
f . In particular, all lifts of the identity automorphism form
the group CT(p) of covering transformations. If the covering graph (and hence the
base graph) is connected, then CT(p) acts semiregularly on vertices and on darts
of ~
X. The covering projection of connected graphs is regular whenever CT(p) acts
regularly on each bre.
There exists an action of the set of walks W on the vertex-set of ~
dened
by ~ u
W is the unique lift of W such that beg
u. In
other words, we have (~u
u. The mapping
~
u  W denes a bijection b beg W ! b end W . Homotopic walks have the
same action. In particular, W u and  u have the same action on b u . The walk-
action implies that coverings (of connected graphs) can be studied from a purely
combinatorial point of view [35]. A voltage space on a connected graph
dened by an action of a voltage group on a set F , called
the abstract bre, and by an assignment  : D ! such that  x This
assignment extends to a homomorphism  carrying
the same voltage. The group Loc called the local group
at the vertex u. As the graph is assumed connected, the local groups at distinct
vertices are conjugate subgroups, and if any of them is transitive we call such a
voltage space locally transitive. With every voltage space on a connected
graph inv) we can associate a covering X. The
graph
as the vertex-set and ~
as the dart-
set. The incidence function is beg(x; and the switching involution
inv is given by (x; The covering graph is connected if and
only if the voltage space is locally transitive. In particular, the Cayley voltage space
(;; ), where acts on itself by right multiplication, gives rise to a regular covering.
Conversely, each covering of a connected base graph is associated with some voltage
space, and each regular covering is associated with a Cayley voltage space (;; ),
3 Action graphs
Let G be a (nontrivial) group acting (on the right) on a nonempty set Z and let
S  G be a Cayley set, that is, ; S. With the triple (Z; G; S)
we naturally associate the action graph
G;
We shall actually need to consider
Cayley multisets, that is, S has repeated elements (where for each s 2 S the elements
s and s 1 have the same multiplicity). Our denition of a graph must then be
extended accordingly.
Example 3.1 The action graph of a group G, acting on a one-element set relative
to a Cayley (multi)set S, is called a monopole and denoted by mnp(S).
Example 3.2 The graph Act(HjG; G; S) is the Schreier coset graph Sch(G; H;S).
By taking we get the Cayley graph Cay(G; S) and a monopole,
respectively.
Example 3.3 Let  be permutations of a nite set Z. By representing
each of these permutations pictorially in the obvious way we obtain the action graph
for the permutation group relative to the symmetrized generating
(multi)set f 1
g.
Example 3.4 A nite oriented map M is a nite graph, cellularly embedded into
a closed orientable surface endowed with a global orientation. Let D be the dart-
set of the embedded graph, L its dart-reversing involution, and R the local rotation
which cyclicaly permutes the darts in their natural order around vertices consistently
with the global orientation. In studying the combinatorial properties of such a map
we only need to consider the permutation group hR; Li on D (together with the
generating set fR; Lg), and consequently, its Schreier representation. See Jones and
Singerman [25]. Equivalently, we only need to consider the action graph of the group
hR; Li acting on D relative to the Cayley set fR; R 1 ; Lg. This graph, here denoted
by Map(D;R;L) or sometimes by Act(M ), is also known as the truncation of the
map [40].
More generally, maps on all compact surfaces can be viewed combinatorially in
terms of certain permutation groups and their generators, as shown by Bryant and
Singerman [10]. For closed surfaces, the associated action graphs correspond to
graph encoded maps of Lins [30].
A walk W in the action graph Act(Z; G; S) denes a word w(W
the alphabet S. Conversely, if w 2 S  is a word, then W (z; w) denotes the (set of
starting at z 2 Z and determined by w. The fact that in the
case of repeated generators there is no bijective correspondence between words over
S and walks, rooted at a chosen vertex, is a minor technical di-culty which we
usually (but not always) can ignore. The action graph is connected if and only if
S generates a transitive subgroup of G. Without loss of generality we can in most
cases assume that the action is transitive and that the Cayley (multi)set generates
the group.
Morphisms arising from coverings of actions
A mapping
Z  ~
is a morphism of action graphs
G; ~
only if
z (~s)); (1)
Zg is a collection of mappings ~
z (~s) and ( ~ z
This follows directly from the denition of a graph morphism. In particular, morphisms
arising naturally from coverings of actions can be viewed as graph covering
projections (by taking the Cayley (multi)sets to correspond bijectively in a natural
way). We state this formally as a theorem, and list some of the well-known special
cases and applications.
Theorem 4.1 Let (;
be a covering of actions and let ~
G be
a Cayley (multi)set. Consider
S) as a multiset in a bijective correspondence
with ~
S. Then the induced graph morphism p
G; ~
G; S) is a covering projection of action graphs.
Proof. The mapping
S satises (1) and (2). Hence
S is a graph
morphism. Since it is onto with qj ~
S a bijection, it is a covering projection.
Example 4.2 Let the action be transitive. Then the mapping G;
Sch(G; G b ; S), where c(b  g, is an equivariant isomorphism.
Example 4.3 Let H  H 0  G. Then
g, is an equivariant covering projection.
Example 4.4 Let K / G. Then is an invariant
1-fold covering projection, and hence an invariant isomorphism.
Example 4.5 Let (id;
G) be an invariant covering of actions.
Then Act(Z; G; S) is invariantly isomorphic to Act(Z;
G; q(S)). Thus, in studying
action graphs we may restrict to faithful actions by taking
similar result dealing with isomorphisms of Cayley digraphs can be found in [22].
Example 4.6 A homomorphism ~
of oriented maps is a morphism of the
underlying graphs which extends to a mapping between the supporting surfaces.
Topologically it corresponds to a branched covering with possible singularities in
face-centres, edge-centres and vertices. Combinatorially we have a mapping of the
respective dart-sets  : ~
D such that (~x  ~
This together with ~
R 7! R denes a covering of actions and consequently,
a covering projection of action graphs Map( ~
Example 4.7 Recall from Example 2.3 that transitive and faithful actions of quotient
groups of G can be \modeled by conjugacy classes of subgoups" in G. It follows
that there exists a covering projection
arising from actions (where only if G Q
b is contained in a conjugate
subgroup of G Q 0
b . A special case is essentially considered in [50]. The situation as
described above is encountered in the theory of maps and hypermaps.
Example 4.8 Oriented maps and their homomorphisms can be modeled by conjugacy
classes within triangle groups, see Jones and Singerman [25]. The idea extends
to all maps [10] and even hypermaps [27].
5 Structure-preserving morphisms
Nonisomorphic actions can give rise to isomorphic graphs, as shown by Examples 4.4,
4.5 and by Example 5.1 below. Also, isomorphic actions can have isomorphic graphs
with no graph isomorphism arising from an isomorphism of actions, see Example 5.2.
Example 5.1 The triangular prism is a Cayley graph for the groups S 3 and ZZ 6 . It
is also an action graph for the group S 4 , obtained by representing S 4 as the subgroup
of S 6 generated by permutations (12)(45)(36), (23)(56)(14) and (13)(46)(25). See
also Example 10.1.
Example 5.2 Take a Cayley graph Cay(G; S) where the generating set S is not a
CI-set. Then there is a generating Cayley set T with Cay(G; S)
that no automorphism of G maps S onto T .
In view of these remarks we note the following. When considering an action graph
as having a certain structure arising from the action, we are actually considering
the induced equivariant covering Act(Z; G;
G; ~
G; S) is structure-preserving if there exists a mapping of the
monopoles mnp( ~
together with mnp( ~
is a morphism of covering projections. In other words,  does not depend on the
S. For example, coverings arising from coverings
of actions are structure-preserving, with mnp( ~
Proposition 5.3 Let
G; ~
G; S) be a structure-preserving
covering, where ~
S and S are generating (multi)sets and G is faithful.
Then this covering arises from a covering of actions.
Proof. By induction we have (~z  ~
~
Z and any choice of generators ~ s
S. Let ~ s 1 ~
As
is onto and G faithful, we have (~s 1 Hence extends to a
homomorphism, as required.
Example 5.4 A covering projection of action graphs Map( ~
such that ~
R 7! R and ~
arises from a covering of actions h ~
hence represents a homomorphism of the respective maps.
Although coverings of action graphs, even isomorphisms, in general do not arise
from actions nor are at least structure-preserving, we may still ask the following.
Let Act( ~
G; ~
G; S) be covering projections. Is there an
action-structure for the graph X (respectively, ~
X) such that these projections arise
from coverings of actions?
Theorem 5.5 Let
G; ~
be a covering projection. Then ther
exists an action graph structure for X such that  +  is equivalent to a covering
arising from actions if and only if there exists a covering projection
which makes the following diagram
G; ~
y
y
commutative. In this case the action-structure for X can be chosen in such a way
that the respective covering is equivariant.
Proof(Sketch). If  +  is equivalent to a projection arising from a covering of
actions, then such a decomposition clearly exists. Conversely, let Z be the vertex-set
of X. One can show easily that z  ~
g), ~ z 2  1 (z), is a well dened action
of ~
G on Z, with
G) an equivariant covering of actions. The
projection
G; ~
G; ~
S) is equivalent to  + .
We can interpret Theorem 5.5 by saying that a quotient of a Schreier coset graph
decomposing the natural projection onto a monopole is again a Schreier coset graph
of the same group. Stated in this form, the result is due to  Siran and
Skoviera [50].
We now turn to the second question above. We assume that (Z; G) is transitive
and that S is a generating Cayley (multi)set. We may also assume that the covering
projection
G; S) is given by means of a voltage
space G; S).
Theorem 5.6 With the notation and assumptions above there exists an action graph
structure for Cov(F; ; ) such that the natural projection
completes the diagram
G; S)
y
y
Moreover, if G is faithful then p  is equivalent to a covering arising from actions.
Proof. The derived graph has Z F as the vertex-set and Z  S  F as the dart-
set, with the incidence function and the switching involution being, respectively,
By the unique walk lifting,
the collection of closed walks in Act(Z; G; S) representing the orbits of s 2 S lift to
a collection of closed walks representing a permutation of Z  F which we denote
by  s . This permutation is dened by (z; i)
is a bijection and that  s
s .
Let ~
Sg. The action graph Act(Z  F; ~
G; ~
has Z S as the vertex-set and Z F  ~
S as the dart-set. The incidence is given by
beg(z; and the switching involution is inv(z;
The mappings id on vertices and (z; s; i) 7! (z; dene an isomorphism
G; ~
S). This induces a projection Act(Z  F; ~
G; ~
G; S) equivalent to p  , and the natural projection Act(ZF; ~
G; ~
induces an equivalent natural projection
S) making the required
diagram commutative.
The last statement in the theorem follows by Proposition 5.3.
Example 5.7 Let a connected graph Cov(F; ; ) be a covering of the action graph
Map(D;R;L) associated with a map M , and let Cov(F; ; ) inherit the action-
structure as in Theorem 5.6. Since L is an involution, Cov(F; ; ) is the action
graph Map(D  F
M , and the covering projection essentially
arises from the map homomorphism ~
M !M , by Example 5.4.
This shows that homomorphisms of oriented maps can be studied just by considering
coverings of associated action graphs. Compare with the discussion on Schreier
representations of maps in [41]. We dene a map homomorphism ~
M to be
regular if Map( ~
Map(D;R;L) is a regular covering. See also [36].
Finally, let us brie
y consider the following question. What is the necessary and
su-cient condition for a connected graph as in Theorem 5.6 to be the
Cayley graph of the group ~
First of all,  s 1
G (z;i) if and only if s 1
F for each z 2 Z. Thus, assuming that G is faithful and the covering is regular, the
answer to the above question is the following: any closed walk with trivial voltage
must correspond to a relation s 1 and in this case, all closed walks corresponding
to this word must have trivial voltage. In particular, a regular covering
of a Cayley graph as in Theorem 5.6 is the required Cayley graph if and only if
the following holds: whenever a closed walk has trivial voltage then all closed walks
corresponding to the respective word must have trivial voltage. This condition is
equivalent to saying that the equivariant group lifts, see Section 8 and [35].
Example 5.8 Let ~
M !M be a regular homomorphism of oriented maps, where M
is a regular map (see Section 7). Since the action graph Act( ~
M ) can be reconstructed
from the action graph Act(M) as in Theorem 5.6 (see Theorem 6.1), it follows that
~
M is a regular map if and only if AutM lifts (see Section 7 and Example 8.9, and
also [36]).
6 Reconstruction
Let
be a covering of transitive actions, let ~
G be a generating
Cayley (multi)set and
S) a (multi)set in bijective correspondence with
~
S. We would like to reconstruct the action graph Act( ~
G; ~
S) from Act(Z; G; S) in
terms of voltages.
This can be done by means of a canonical voltage space ( ~
G; ) (relative to
(; q)) on Act(Z; G; S), with voltages on darts dened by the rule
The derived covering graph Cov( ~
G; ) has vertex-set ~
Z and the dart-set
~
Z. The incidence function beg : ~
V is given by the projection
beg(z; s; ~
z), and the switching involution is inv(z; s; ~
(s). The corresponding local group is Its action on
~
Z is, modulo relabeling, the same as the action of W b on the vertex bre over b in
G; ). But W b and q 1 (G b ) also act on the bre b b in Act( ~
G; ~
S). In fact,
is an invariant covering of actions.
Theorem 6.1 With the notation above, the component C(b; ~ b) of Cov( ~
G;
the vertex (b; ~ b), consists exactly of all vertices of the form (z; ~ z),
(~z), and the restriction G; S) is equivalent to
G; ~
G; S). (If ~
G is a permutation group, then the action graph
structure imposed on C(b; ~ b) as in Theorem 5.6 coincides with Act( ~
G; ~
S).)
Next, all restrictions of
G; G; S) to its connected components
are equivalent to
G; ~
G; S) if and only if the
restrictions of the action of q 1 (G b ) on all its orbits have the same conjugacy class
of stabilizers. In particular, let the action of ~
G be such that no stabilizer is properly
contained in another stabilizer (say, the group is nite). Then all restrictions of p
to its connected components are equivalent to p ;q if and only if q( ~
Proof. Let (z; ~
u) be in the same component as (b; ~ b),
vertices in this component
are of the required form. If (z; ~
z) and (u; ~ u) have the same label ~
Hence no two vertices are labeled by the same label. Moreover,
all labels from ~
Z actually appear since ~
S generates ~
G and ~
G is transitive on ~
Z.
The bre over b in C(b; ~ b) is labelled by the orbit of Loc b on ~
Z which is precisely
It follows that the actions of W b on bres over b in C(b; ~ b) and
G; ~
are essentially the same. Hence G; S) and
G; ~
G; S) are equivalent. The explicit graph isomorphism which
establishes this equivalence is (z; ~
z) 7! ~ z on vertices and (z; s; ~
z) 7! (~z; ~ s) on darts. If
~
G is faithful, then the action graph structure imposed on C(b; ~ b) as in Theorem 5.6
obviously coincides with Act( ~
G; ~
S).
Clearly, all restrictions of p  to the components of Cov( ~
G; ) are equivalent if
and only if the induced actions of Loc its orbits in ~
Z are equivari-
antly isomorphic, that is, all of these actions must have the same conjugacy class of
stabilizers in Loc b .
Observe that Loc b
G ~ z for ~
~
G ~
Now, if all stabilizers of ~
G are contained in Loc b , then all the above actions of
do have the same conjugacy class of stabilizers. Conversely, the fact that
each
~
G ~
is also the stabilizer of some point ~ z 2  1 (b) implies
~
G ~ z  ~
G ~ u . Since the action of ~
G is not pathological, we have equality, and hence each
stabilizer of ~
G must be contained in Loc This condition can be further
rephrased as follows. Since q is onto and ~
G ~ z , ~ z 2 ~
Z are conjugate subgroups, we
have
G. Thus, q( ~
Conversely, if q( ~
then q( ~
G ~
. This completes the proof.
Example 6.2 The action graph Act( ~
G; ~
S) can be reconstructed from Act(Z; G; S)
by taking just any connected component of the derived covering, for instance, when
~
G (or G) acts with a normal stabilizer. A special case is encountered when reconstructing
Cayley graphs form Cayley graphs of quotient groups [19].
Example 6.3 Consider the dihedral group
1i with subgroups
Then Sch(G; H;S) equivariantly covers Sch(G; H 0 ; S). Since not all conjugates of
H, the graph Sch(G; H;S) cannot be reconstructed by taking just any
connected component of the derived covering Cov(HjG; G; ).
In this particular case we can also apply the Burnside-Frobenius counting lemma.
Namely, the action of H 0 on the cosets of H has two orbits, whereas the derived
covering is 9-fold.
7 Automorphisms
We henceforth assume that actions are transitive and that Cayley (multi)sets generate
the groups in question. A bijective self-mapping  +  of Z +ZS is an automorphism
of Act(Z; G; S) if and only if (z;
a collection of bijective self-mappings of S satisfying (z
Studying general automorphisms, even the subgroup of
structure-preserving ones, is di-cult. Next in the line is the subgroup Aut S (Z; G) of
extends to (or just is) an automorphism
of G. Proposition 5.3 implies Proposition 7.1.
Proposition 7.1 Let a transitive action (Z; G) be faithful, and let S  G be a
generating Cayley (multi)set. Then each automorphism of Act(Z; G; S) of the form
is an action-automorphism.
Let Aut S denote the subgroup of S-automorphisms
of G, and let Adm S
its S-admissible subgroup formed
by automomorphisms which preserve S as well as the conjugacy class of stabilizers
of G (as a set). Of course,  +  is an action-automorphism of Act(Z; G; S) if and
only if (;
Z G. In particular, we can identify Eq(Z)G ,
the equivariant group of automorphisms of Act(Z; G; S), and the equivariant group
of the action, Aut(Z)G . It is easy to see that the projection Aut S (Z;
is a group epimorphism with kernel Aut(Z)G . We state this observation
formally.
Theorem 7.2 The group Aut S (Z; G) of action-automorphisms of Act(Z; G; S) is
isomorphic to an extension of the equivariant group Aut(Z)G by Adm S
Z G.
While Aut(Z)G is isomorphic to NG (G b )=G b , the identication of Adm S
Z G and
the extension itself might not be easy. Here is a simple and well-known example.
Example 7.3 In view of Proposition 7.1 there are two kinds of automorphism of
Cayley graphs. Those for which the mapping of darts is not constant at all points,
and those which are action-automorphisms. Let + be an action-automorphism.
a (g), for some a 2 G and 2 Adm S
G.
Moreover, the assignment (a; is an isomorphism G
Aut S (G; G) r . Hence the group of action-automorphisms Aut S (G; G) r of Cay(G; S)
is isomorphic to a subgroup in the holomorph of G.
The group Aut S (G; G) r can as well be characterized as the normalizer of the left
regular representation f a;id j a 2 Gg of G within the full automorphism group of
Cay(G; S) [18].
Example 7.4 From the very denition it follows that the automorphism group
AutM of an oriented map M can be identied with the equivariant group Aut(D) hR;Li
[25].
Example 7.5 An oriented map is called regular if its automorphism group acts
transitively (and hence regularly) on the dart-set of the underlying graph. Recall
that the equivariant group acts regularly if and only if the group itself is regu-
lar. Therefore, a map is regular if and only if Map(D;R;L) is a Cayley graph
for the group hR; Li [25, 40]. Since any Map(D;R;L) is equivariantly covered by
every map is a (branched) regular quotient of some regular
map [25, 26, 46]. The idea extends to maps on bordered surfaces [5].
As a last remark, let us ask what are the necessary and su-cient conditions
for a transitive faithful action (Z; G) to extend to a group of automorphisms of
G; S). This problem is of interest [45] (however, action graphs in [45] dier
from ours), and di-cult in general. But let us assume that the induced automorphism
group preserves the natural structure as a covering of mnp(S). Then the
answer is trivial.
Proposition 7.6 Let the action (Z; G) be transitive and faithful, and let S  G
be a generating Cayley (multi)set. Then T
g, is a group of (action) automorphisms of Act(Z; G; S) if and only if
S is a union of conjugacy classes. In particular, T (G) acts as a subgroup of the
equivariant group if and only if the action graph is a Cayley graph Cay(G; S) and G
is abelian.
Other types of symmetries of action graphs will not be discussed here. Arc-
transitivity of Cayley digraphs is considered, for instance, in [2, 22].
8 Lifting and projecting automorphisms
G; ~
G; S) be a covering arising from transitive actions,
where ~
S and
are generating Cayley (multi)sets. The problem of lifting
automorphisms has recently obtained considerable attention [4, 5, 6, 9, 15, 23, 24,
in various contexts. From the general theory we infer that
the lifting condition, expressed in terms of the canonical voltages valued in ~
G, reads:
An automorphism  lifts along p ;q if and only if there exists ~ z 2 b b such that,
for each W 2 W b ,
G ~ b if and only if  W 2 ~
G ~
However, we here explore the possibility that the lifting condition be expressed
without the usual explicit reference to mappings of closed walks and their voltages,
but, rather, expressed in terms of certain subgroups of G and ~
G. To this end we
have, in spite of the fact that coverings arising from actions are somewhat peculiar,
restrict our considerations either to a very special class of action-automorphisms
(the equivariant group), or else to action-automorphisms with addtional requirements
imposed on the covering of actions (Example 8.2). We also note that the
lifts of action-automorphisms, although structure-preserving, need not be action-
automorphisms.
Example 8.1 Let ~
G be faithful. Then, by Proposition 7.1, a lift of an action-
automorphism of Act(Z; G; S) is an action-automorphism of Act( ~
G; ~
S),.
Example 8.2 Suppose that a covering of actions is equivariant. Then the conclusion
as in the previous example holds, too. Moreover, from (3) we easily derive that
an action-automorphism  lifts if and only if there exists g 2 G such that
g. (An alternative direct proof avoiding (3) is readily
at hand and is left to the reader.) In particular, action-automorphisms do lift along
the equivariant covering Cay(G; G; S).
We now focus our attention on the equivariant group Eq(Z)G of Aut(Z; G; S).
That one can derive a reasonable lifting condition in terms of subgroups of ~
G and G
is not surprising because with equivariant automorphisms we could as well consider
just coverings of actions.
Theorem 8.3 The equivariant group Eq(Z)G lifts along
G; ~
G; S) if and only if q(N ~
G ~ b )) intersects every coset of G b within NG (G b ),
and the lifted group is then a subgroup of the equivariant group Eq( ~
G . In particu-
lar, if the covering projection is regular, then Eq(Z)G lifts if and only if NG (G b )
q(N ~
Proof. We present a proof which avoids the reference to (3). Clearly, a lift of
an equivariant automorphism is equivariant. Consider a pair of equivariant automorphisms
of the covering graph and of the base graph, respectively. Their action
on vertices is given, relative to ~ b and
G ~ b , and  c (b
be a lift of  c +  c  id, that is, let ~ ~
We easily get q(~c) 2 G b c. Conversely,
if c and ~ c satisfy this condition, then ~  ~ c
~ c  id is a lift of  c id. The lifting
condition can now be expressed as: for each c 2 NG (G b ) there exists ~ c 2 N ~
such that q(~c) 2 G b c. The claim follows.
The covering projection p ;q is regular if and only q 1
G ~ b ), by Theorem
9.1 below. This implies G b  q(N ~
G ~ b )), and hence the lifting condition now
obviously reduces to NG (G b )  q(N ~
G ~ b )). The alternative form follows because
contains Ker q.
Example 8.4 Let the group ~
G act with a normal stabilizer. Then the equivariant
group lifts. In particular, Eq(Z)G lifts along
G; ~
G; S).
Example 8.5 Let ~
M !M be a homomorphism of oriented maps. If ~
M is a regular
map, then AutM lifts [36].
Example 8.6 The lift of the equivariant group Eq(Z)G along a regular covering
projection p ;q is isomorphic to q 1 (NG (G b ))= ~
G ~ b .
Proposition 8.7 Let the covering
G; ~
Cay(G; S) be regular. If
the equivariant group of Cay(G; S) lifts, then Act( ~
G; ~
S) is isomorphic to the Cayley
graph Cay( ~
G ~
S).
Proof. By Theorem 8.3 we have q(N ~
G. Thus N ~
coset of Ker q. Since Ker q  q 1
Theorem 9.1
below), N ~
contains Ker q. Hence N ~
G, and the proof follows.
Example 8.8 Consider a regular covering
G; ~
~
G is faithful. Then Act( ~
G; ~
S) is isomorphic to the Cayley graph Cay( ~
G; ~
S) if and
only if the equivariant group of Cay(G; S) lifts, by Example 8.4 and Proposition 8.7.
In view of the lifting condition (3) we may rephrase this as in Section 5.
Example 8.9 Let ~
M be a regular homomorphism, where M is a regular
map. If AutM lifts, then ~
M is also a regular map. In view of Example 8.5 we
obtain the if and only if statement of Example 5.8. See also [20, 36].
Let us now consider projecting automorphisms of Act( ~
G; ~
along p ;q . An
automorphism ~
projects whenever each vertex-bre is mapped onto some vertex-
bre and each dart-bre is mapped onto some dart-bre. If the covering is regular,
then an automorphism projects if and only if it normalizes the group of covering
transformations. This is actually a theorem of Macbeath [37] which holds for general
topological coverings as well as in our combinatorial context. A similar result for
digraphs is proved in [39].
Note that projections of action-automorphisms are structure-preserving but need
not be action-automorphisms. One particular instance when such projections are
indeed action-automorphisms is when the covering is equivariant. The case when G
acts faithfully is another. In general, the following holds.
Proposition 8.10 Suppose that an action-automorphism ~
~
of Act( ~
G; ~
projects along
G; ~
G; S). Then the projected automorphism
is an action-automorphism of Act(Z; G; S) if and only Ker q is invariant for ~
.
Proof. Let   be the projected automorphism. We know that is dened
q 1 on S. Now extends to an automorphism of G if and
only if Equivalently, we must have
Ker q, that is, ~
Theorem 8.11 An action-automorphism ~
of Act( ~
G; ~
projects along
G; ~
G; S) if and only if there exists ~
G such that
~
and ~
Proof. First of all, if an action-automorphism is vertex-bre preserving, then
it is also dart-bre preserving. Moreover, it is enough to require that just one
vertex-bre is mapped to a bre. The proof of this fact is left to the reader. It
follows that ~
~
projects if and only if ~
maps
Writing ~  ~
g and taking into account that the stabilizers are conjugate
subgroups, we obtain the desired result.
Example 8.12 An action-automorphism ~
of Act( ~
G; ~
projects along
G; ~
only if ~
(Ker Ker q, and the projection
is necessarily an action-automorphism.
Theorem 8.13 The group Eq( ~
G projects along
G; ~
G; S)
if and only if N ~
(equivalently, q(N ~
)). The projected
group is a subgroup of Eq(Z)G . For regular coverings, the condition simplies
to
Proof. Clearly, the projection of an equivariant automorphism is equivariant. By
Theorem 8.11, an automorphism ~
c  id, where ~
c~g and ~ c 2
G ~ b , projects if and only if there exists ~ g 2 ~
G such that ~ b  ~ and
~
This is equivalent to saying that N ~
intersects the coset
~
should intersect every coset of
~
G ~ b within N ~
implying that N ~
should contain N ~
claimed. The alternative form is also evident. direct
proof similar to the proof of Theorem 8.3 is left to the reader.) The rest follows by
Theorem 9.1.
Example 8.14 Let G act with a normal stabilizer. Then the group Eq( ~
G projects.
In particular, it projects along
G; ~
Example 8.15 Let ~
M be a homomorphism of oriented maps, where M is a
regular map. Then Aut ~
projects [36].
Corollary 8.16 Let the group Eq( ~
G project along
G; ~
G; S).
Then Act(Z; G; S) is isomorphic to the Cayley graph Cay(G=GZ ; S).
Proof. By Theorem 8.13 we have
G. Hence G b is normal in G, and the
proof follows.
Example 8.17 Let ~
M be a homomorphism of oriented maps, where ~
M is a
regular map. In view of Example 8.15 and Corollary 8.16 the group Aut ~
projects
if and only if M is also a regular map. (The homomorphism itself must then be
regular, see Example 9.3.)
Corollary 8.18 Let the covering projection
G; ~
G; S) be
regular. Then the equivariant group Eq(Z)G lifts and the equivariant group Eq( ~
G
projects if and only if q(N ~
In this case, Eq(Z)G lifts to Eq( ~
G
and Eq( ~
G projects onto Eq(Z)G .
Proof. By Theorems 8.3 and 8.13 we must have
q(N ~
and the claim follows. The last statement is evident as
well.
Example 8.19 The projection
G; ~
Cay(G; S) is regular (see Example
9.3). The left regular representation of G lifts to the left regular representation
of ~
G, and hence the latter projects onto the former. In particular, if ~
a homomorphism of regular maps, then Aut M lifts to Aut ~
M and Aut ~
projects
9 The structure of lifted groups
Theorem 9.1 Let a covering projection
G; ~
G; S)
arise from a covering of transitive actions, where ~
S and
are generating
Cayley (multi)sets. Choose ~ b 2 ~
Z and base-points. Then:
(a)
is a subgroup of Eq( ~
G .
G ~ b g is
isomorphic to (q 1
G ~ b .
(c) The covering projection p is
G ~ b ]-fold, and is regular if and only if
~
Proof. The statement (a) is obvious. Since ~
G is transitive on ~
Z we can explicitly
calculate the elements of Aut( ~
G relative to ~ b as ~ ( ~ b  ~
G ~ b . Now b.
Consequently, ~ c 2 q 1 (G b ), giving (b).
The rst statement of (c) follows from the fact that the covering is connected.
Indeed, the group q 1 acts transitively on the bre  1 (b) and has ~
G ~ b as its
stabilizer. The covering is regular, by denition, if CT(p) is transitive on  1
)g. But this holds if and only if q 1
part (c) follows.
Example 9.2 Let H  H 0  G, and let
be the corresponding covering projection, where g. Then
is isomorphic to (H 0 \N(H))=H.
The covering projection is [H and is regular if and only if H / H 0 .
Example 9.3 A covering
G; ~
G; S) is always regular. Hence
a homomorphism ~
of oriented maps, where ~
M is a regular map, must be
a regular homomorphism. In particular, homomorphisms between regular maps are
regular [36].
A lifted group of automorphisms is an extension of the group of covering transformations
by the respective group of the base graph. This extension is di-cult to
analyze in general [9, 20, 33, 35, 36, 51]. We end this section by considering the
case when the equivariant group lifts as a split extension along a covering projection
arising from actions. As the equivariant group acts without xed points, each orbit
of an arbitrary complement to CT(p) within the lifted group intersects each bre
in at most one point (thus forming an invariant transversal). This is equivalent
with the requirement that the covering projection be reconstructed by means of a
voltage space for which the distribution of voltages is well behaved relative to the
action of the equivariant group. The claim takes a particularly nice form whenever
the covering projection is regular [33, 35]. A straightforward application of these
considerations to regular homomorphisms of oriented maps gives Theorem 9.4. A
direct proof in terms of voltages associated with angles of the map can be found in
[36]. By
we denote the set of all walks with endvertices in a subset of vertices
Theorem 9.4 Let ~
M be a regular homomorphism of oriented maps, and let
be an orbit (or a union of orbits) of a dart in M relative to AutM . Then AutM
lifts as a spit extension of CT (the lift of the identity automorphism) if and only
if the covering projection of action graphs Act( ~
can be reconstructed
by means of a Cayley voltage space (CT; CT; ) such that the set of walks fW 2
in Act(M) is invariant for the action of AutM . Moreover, the
extension is a direct product if and only if Act( ~
can be reconstructed
by a Cayley voltage space (CT; CT; ) such that each of the sets fW 2
is invariant for the action of AutM .
Proof. The map automorphism group corresponds to the equivariant group in the
associated action graph, and the lift of the identity corresponds to the group of
covering transformations for the regular covering projection of the respective action
graphs. The theorem follows by applying Theorems 9.1 and 9.3, and Corollaries 9.7
and 9.8 of [35].
Generators and relations
a nonempty antisymmetric subset, that is, ! S \
is either
empty or else all of its elements are of order 2. With (Z; G) and ! S we associate
the action digraph Act(Z; G; with the vertex-set Z and the arc-set Z  ! S , where
in the case of action graphs it is sometimes
necessary to consider the set ! S as a multiset. The underlying graph of Act(Z; G;
is the action graph act(Z; G; ~
G;
). (Note that involutory loops
collapse to semiedges.) Omitting formal basic denitions we only mention that
epimorphisms of actions give rise to covering projections of action digraphs.
The study of group presentations involves a variety of techniques, see [13, 31, 32,
48] and the references therein. Action digraphs can often provide much insight to a
formal algorithmic approach, and were (in disguise) at least partially present in the
original works of Reidemeister and Schreier.
Choose a spanning tree in Act(Z; G; ~
S), where (Z; G) is transitive and ~
generates
G. Each cotree arc gives rise to a unique fundamental closed walk based at z 2 Z,
and the set of all such walks generates the set of all closed walks at z, up to reduction.
Thus, if ~
C is a set of labels bijectively associated with all the cotree arcs, which
evaluate to words in ( ~
dened by the fundamental closed walks rooted at
z 2 Z, then each element of G z , expressed as a word in ( ~
can be written
as a word in ( ~
. This is done by trailing the closed walk associated with a
given word in ( ~
simultaneously keeping track of the labels in ~
when traversing a cotree arc. The process is known as the rewriting process relative
to z 2 Z. A variant of the Schreier-Reidemeister theorem now states the following.
Ri be a presentation of G, and let RewR be the set of (reduced) words
in ( ~
obtained from all the relators in R by a rewriting process relative
to all z 2 Z. Then the stabilizer G b has the presentation h ~
C; RewRi. Many of
the generators and relators obtained by this method can be redundant. However,
sophisticated techniques for simplifying the presentation do exist in certain cases
[12, 13, 32, 48, 52].
An action digraph Act(Z; G; ~
S), where ~ S generates G, obviously determines the
group G=GZ up to isomorphism (also if G is not transitive). Suppose that the
action digraph is nite. Denote by ~
1 the generators of the stabilizer G b 1
, expressed
as words in (
associated with fundamental closed walks at b 1 relative
to a spanning tree in the appropriate component of Act(Z; G; ~
S). By repeating
this process on Act(Znfb 1
on, we can
recursively construct a generating set for the pointwise stabilizer GZ . Hence if G is
faithful, we can nd a presentation of G. If j ~
then the number
of generators of GZ obtained in this way can amount up to (n 1)m!+ 1. Thus, the
method is not practical unless one can detect enough many redundant generators at
each step, or has su-cient control over the recursive construction of the generators.
As for the improvements which allow eective computer implementation we refer to
[11, 12, 48] and the references therein.
Example 10.1 We leave to the reader to check that the following three permutations
in the symmetric
a subgroup which is isomorphic to S 4 .
Despite the remarks above, Act(Z; G; ~
proves useful in gathering at least partial
information about the dening relations, particularly when its underlying graph
is highly asymmetric with special structure. The idea is to use graph-theoretical
properties of Act(Z; G; ~
S) to derive such information. The following example is
taken from [34].
Example 10.2 Consider the alternating group A n , where n  11 is odd, and the
generators
analysis of the action digraph shows that in the Cayley
graph the cycles of girth-length, which is 6, arise essentially
from the relation (ab 1 that cycles of length n arise essentially from the
obvious relations a This information is crucial in proving that the above
Cayley graph is 1/2-transitive.
What we have discussed so far can be applied to a problem encountered with lifts
of automorphisms. Let be a covering projection of connected
graphs (or even more general topological spaces, see [33]), given by means of a voltage
space acts faithfully on F . A necessary condition (also su-cient
if the covering is regular) for an automorphism to lift is that the set of all closed
paths with trivial voltage be invariant under its action [33, 35]. In order to test
this eectively (assuming of course, that the covering has nite number of folds and
that the fundamental group of X is nitely generated) we need the generators of the
kernel of  :  b ! , expressed in terms of a generating set ~
S of  b , save for those
cases where ad-hoc techniques apply. One possibility is to consider the auxiliary
regular covering X. The required generators of Ker  are
then obtained by projecting the generators of ( ~ b; Cov), where ~ b 2 b b . However,
this requires the construction of Cov(;; ), which is not always appropriate.
A better alternative is to consider the fundamental group  b acting on by right
multiplication  (). The stabilizer of this action is Ker , and so the required
generators can be found by means of a spanning tree in Act(; b ; ~
S)).
It is close to rst constructing the coset representatives of Ker , that is, nding a
closed path (rooted at the based point) with voltage , for all  2 , and then
applying the Schreier method. Another possibility is to consider the action of  b
on the abstract bre F given by i  (). The kernel Ker  is then equal to
the pointwise stabilizer of this action. Thus, the required generators can be found
recursively by considering the action digraph Act(F;  b ; ~ S).
A similar problem is to construct a generating set for the trivial voltage paths
with endpoints in an orbit of a given group A of automorphisms of X. Namely, a
necessary and su-cient condition for A to lift along a regular covering projection as
a special kind of split extension of CT(p) (one with an invariant transversal [33, 35])
is that the set of paths as above be invariant for the action of A (recall Theorem 9.4).
Suppose that X is a graph
and
a vertex orbit. Introduce a new vertex B not in X,
and connect B with all the vertices in
Moreover, extend the voltage assignment
so that these new edges carry the trivial voltage. The required generating set of
walks is obtained in the same way as before by considering the extended graph with
B as the base point. Note that the group A has the required type of lift if and
only if, viewed as the stabilizer of B in the extended graph, lifts along the extended
covering projection. (The idea clearly extends to nite CW-complexes.)
The preceding discussion is summarized in the following theorem.
Theorem 10.3 With notation and assumptions above, the problem whether a given
group A of automorphisms of a graph X (or a more general topological space) lifts
along a regular covering projection given by a faithful voltage space can be
tested in time, proportional to the number of generators of A, multiplied by the time
required for the construction of Cay(; ( ~
and its spanning tree (or multiplied by
the time required for the construction of Act(F;  b ; ~
S) and nding the generators of
the pointwise stabilizer).
If X is a graph (or a nite CW-complex), a similar statement holds for the
problem whether a given group of automorphisms of X lifts as a split extension of
CT(p) with an invariant transversal.



--R

On group graphs and their fault tolerance
A. group theoretic model for symmetric
Group action graphs and parallel architectures


Homological coverings of graphs
Some applications of graph contractions
Conjugacy graphs with an application to imbedding metric graphs

Foundations of the theory of maps on surfaces with boundary
Cambridge University Press
Construction of de
Generators and relations for discrete groups

Isomorphism classes of concrete graphs coverings

Routage uniformes dans les graphes sommet-transitifs
On the full automorphism group of a graph


Graph homomorphisms: structure and symmetry

Isomorphisms and automorphisms of coverings
Graph covering projections arising from
Theory of maps on orientable surfaces
Theory Ser.

Group actions
Isomorphism classes of graph bundles
Theory Ser.

Combinatorial group theory: Presentations of groups in terms of generators and relations




On a theorem of Hurwitz

Automorphisms of groups and isomorphisms of Cayley digraphs




Vega version 0.2 quick reference manual and Vega graph gallery


Automorphism groups of covering graphs
Computation with


Graph coverings and group liftings
Surfaces and planar discontinuous groups
--TR
Topological graph theory
On group graphs and their fault tolerance
A Group-Theoretic Model for Symmetric Interconnection Networks
Group action graphs and parallel architectures
Lifting map automorphisms and MacBeath''s theorem
Isomorphisms and automorphisms of graph coverings
Which generalized Petersen graphs are Cayley graphs?
Graph covering projections arising from finite vector spaces over finite fields
Automorphism groups of covering graphs
Group actions, coverings and lifts of automorphisms
Isomorphism Classes of Concrete Graph Coverings
Constructing 4-valent <inline-equation> <f> <fr><nu>1</nu><de>2</de></fr></f> </inline-equation>-transitive graphs with a nonsolvable automorphism group
Lifting graph automorphisms by voltage assignments
Strongly adjacency-transitive graphs and uniquely shift-transitive graphs

--CTR
Tomaz Pisanski , Thomas W. Tucker , Boris Zgrabli, Strongly adjacency-transitive graphs and uniquely shift-transitive graphs, Discrete Mathematics, v.244 n.1-3, p.389-398, 6 February 2002
Aleksander Malni , Roman Nedela , Martin koviera, Regular homomorphisms and regular maps, European Journal of Combinatorics, v.23 n.4, p.449-461, May 2002
regular map;voltage group;cayley graph;lifting automorphisms;covering projection;action graph;schreier graph;group action;group presentation