Elementary Abelian Covers of Graphs
ALEKSANDER MALNI ˇC∗
DRAGAN MARU ˇSI ˇC∗ dragan.marusic@uni-lj.si
PRIMO ˇZ POTO ˇCNIK†
IMFM, Oddelek za matematiko, Univerza v Ljubljani, Jadranska 19, 1111 Ljubljana, Slovenija Received November 5, 2001; Revised July 24, 2003; Accepted August 7, 2003
Abstract. LetCG(X) be the set of all (equivalence classes of) regular covering projections of a given connected graphX along which a given groupG ≤AutX of automorphisms lifts. There is a natural lattice structure on CG(X), where℘1 ≤℘2whenever℘2factors through℘1. The sublatticeCG(℘) of coverings which are below a given covering℘: ˜X → X naturally corresponds to a latticeNG(℘) of certain subgroups of the group of covering transformations. In order to study this correspondence, some general theorems regarding morphisms and decomposition of regular covering projections are proved. All theorems are stated and proved combinatorially in terms of voltage assignments, in order to facilitate computation in concrete applications.
For a given prime p, letCGp(X) ≤CG(X) denote the sublattice of all regular covering projections with an elementary abelianp-group of covering transformations. There is an algorithm which explicitly constructsCGp(X) in the sense that, for each member ofCGp(X), a concrete voltage assignment onXwhich determines this covering up to equivalence, is generated. The algorithm uses the well known algebraic tools for finding invariant subspaces of a given linear representation of a group. To illustrate the method two nontrival examples are included.
Keywords: covering projection, lifting automorphisms, Cayley voltages, homological covering, invariant sub- space, lattice, arc-transitive graph, semisymmetric graph, dipole, Heawood graph
1. Introduction
Graphs admitting an imprimitive action of a subgroup of automorphisms arise naturally out of their quotients. In attempting to classify graphs with interesting symmetry properties it is therefore natural to first consider the ‘primitive’ graphs (which is almost exclusively based on the classification of finite simple groups) and then try to explicitly construct the
‘imprimitive’ ones. In many instances the ‘imprimitive’ graphs arise as derived graphs along regular covering projections. Djokovi´c [5] showed that the correspondence between symmetry properties of graphs and symmetry properties of their regular covers is related to the problem of lifting automorphisms.
So the main question addressed in this paper is the following one. For a given connected graphXand a subgroupG≤AutXof its automorphisms, find the setCG(X) of equivalence classes of connected regularG-admissible covering projections℘: ˜X → X, that is, cov- ering projections along whichGlifts. The answer is well understood at some very general
∗Supported in part by “Ministrstvo za ˇsolstvo, znanost in ˇsport Slovenije”, research program no. 101-506.
†Supported in part by “Ministrstvo za ˇsolstvo, znanost in ˇsport Slovenije”, research project no. Z1-3124.
level in view of the fact that the problem of lifting automorphisms was solved in algebraic topology decades ago. However, finding the required covering projectionsexplicitlyis al- gorithmically almost intractable—this largely depends also on how the term ‘explicitly’ is to be understood. As each covering projection of graphs can be, up to equivalence, recon- structed in terms of voltages [11], our understanding of ‘explicitly’ isto display concrete voltage assignmentson the graphX.
Consider the natural partial ordering≤in the setCG(X), where℘1 ≤ ℘2whenever℘2
factors through℘1[24, 25]. Let℘: ˜X → Xbe aG-admissible regular covering projection, and let ˜G≤Aut ˜X be the lift ofG. There is a lattice anti-isomorphism(G,℘):NG(℘)→ CG(℘) between the set of regular covering projectionsCG(℘)⊆CG(X) which are below℘ in the ordering, and the setNG(℘) of normal subgroups of ˜G≤Aut ˜Xwhich are contained in the group of covering transformations CT(℘). So by findingNG(℘) one can determine CG(℘) and moreover,CG(X), sinceCG(X)=CG(℘U), where℘U is the universal covering projection of an appropriate (infinite) tree ontoX.
A regular covering projection isp-elementary abelian if its group of covering transforma- tions is an elementary abelian p-group. In this paper we show how to explicitly construct, for a given prime p, the sublatticeCGp(X)⊆CG(X) of p-elementary abelianG-admissible regular covering projections. Namely, the latticeCGp(X) has a unique maximal element, the p-homological covering℘: Xp → X, which is characterized by having CT(℘) isomor- phic to the first homology groupH1(X;Zp). Since℘is maximal, we haveCGp(X)=CG(℘).
Moreover, findingNG(℘) is now reduced to finding all invariant subspaces for the linear representation ofGonH1(X;Zp). Once these subspaces are found, the elements ofCGp(X) can be explicitly reconstructed in terms of concrete voltage assignments onX.
The paper is organized as follows. In Section 2 we review some preliminary concepts about graphs and (combinatorial) regular covering projections in terms of voltages. In order to have a broader range of applications we allow graphs to have semiedges. (Note that the theory of topological coverings and in particular, standard theorems about lifting automor- phisms as known in topology do not apply directly in this case since a walk of length 1 traversing a semiedge should be considered as homotopically nontrivial.) In Section 3 we prove a general theorem about the existence of certain morphisms between regular cov- ering projections to be used repeatedly later on. In Section 4 we revise some results of Venkatesh [24, 25] about ordering regularG-admissible covering projections. Our treate- ment is combinatorial in terms of voltages and hence differs from the one given in [24, 25].
Moreover, we show how to construct the covering projection(G,℘)(K) (K ∈ NG(℘)) in terms of voltages, see Proposition 4.1(b). In Section 5 we specialize the general consid- erations of previous sections to abelian regular covering projections. This is then used in Section 6, where elementary abelian coverings are treated in detail. The central result, The- orem 6.2, upgrades Proposition 4.1(b); in particular, we show how to construct(G,℘)(K) (K ∈NG(℘)) explicitly if the voltage group is elementary abelian. From this, an algorithm which determines allG-admissiblep-elementary abelian regular covering projections fol- lows (see Corollary 6.5). The method reduces to finding all invariant subspaces of a linear representation of a group on the first homology groupH1(X;Zp). It is generally known that such invariant subspaces can be found by considering the factorization of the respective minimal polynomials. The method generalizes ˇSir´aˇn’s treatement of prime-cyclic covering
projections [22]. Finally, in Section 7 we provide two fairly detailed concrete examples, namely, the elementary abelian regular covering projections of prime-dipoles and of the Heawood graph.
For additional references on graph coverings related to the topics of this article we refer the reader to [1, 11, 12].
2. Preliminaries
2.1. Graphs
For the purpose of this article, agraphis an ordered 4-tuple X =(D,V; beg,inv) where DandV = ∅are disjoint finite sets ofdartsandvertices, respectively, beg : D → V is a mapping which assigns to each dart xitsinitial vertexbegx, and inv : D → Dis an involution which interchanges every dartxand itsinverse dart x−1=invx. If not explicitly given, the four defining parameters of a graph X are denoted byDX,VX, begX and invX, respectively. Theterminal vertexendxof a dartxis the initial vertex of invx. The orbits of inv are callededges. An edge is called asemiedgeif invx=x, aloopif invx =xwhile endx=begx, and is called alinkotherwise.
Walks are defined as sequences of darts where for any two consecutive dartsx,y we have endx =begy. By recursively deleting all consecutive occurrences of a dart and its inverse in a given walk we obtain a reduced walk which we call thereduction. Two walks with the same reduction are calledhomotopic. The naturally induced operation on the set of all reduced b-based closed walks defines thefundamental group π(X,b) at thebase vertex b. Note that the concept of homotopy doesnotexactly correspond to homotopy in the corresponding 1-CW complex associated with a graph. This is due to the fact that a walk of length 1 traversing a semiedge is homotopically nontrivial. Thus, the fundamental group is not a free group in general. (Yet a minimal generating set ofπ(X,b) can be obtained in the standard way employing a spanning tree.) Consequently, the first homology groupH1(X), obtained by abelianizingπ(X,b), is not necessarily a freeZ-module. Namely, letre+rsbe the minimal number of generators ofπ(X,b), wherersis the number of semiedges andreis the number of cotree loops and links relative to some spanning tree. ThenH1(X)∼=Zre×Zr2s. The first homology groupH1(X;Zp)∼=H1(X)/p H1(X) withZpas the coefficient ring can be considered as a vector space over the fieldZp. Observe that
H1(X;Zp)∼=
Zrpe+rs p=2 Zrpe p≥3.
Amorphism of graphs f: X → Xis a function f: VX ∪DX → VX∪DXsuch that f VX ⊆ VX, f DX ⊆ DX, and f begX =begX f and f invX =invX f. The product of graph morphisms is defined as composition of functions. Concepts such asmono-, epi-, iso- and automorphisms are self-explanatory. An important special case of morphisms arises in the context of group actions on graphs. Namely, ifN ≤ AutX is a subgroup of automorphisms letDN = {[x]|x∈ D}andVN = {[v]|v∈V}denote the sets ofN-orbits on darts and vertices ofX, respectively, and let begN[x]=[begx] and invN[x]=[invx].
This defines a graph XN = (DN,VN; begN,invN) together with a natural epimorphism pN: X → XNcalled thequotient projection relative to N.
2.2. Covering projections
A graph epimorphism℘ : ˜X → Xof connected graphs is acovering projectionif℘is a local bijection on darts, that is, for each vertex ˜v ∈ VX˜ the set of darts of ˜X having ˜v as the initial vertex is mapped bijectively onto the set of darts ofX having℘( ˜v) as the initial vertex. The preimages℘−1(v) (v∈ VX) and℘−1(x) (x ∈ DX) arevertex-anddart-fibres, respectively.
Let℘i: ˜Xi → Xi(i=1,2) be covering projections. Amorphismof covering projections
℘1 →℘2is an ordered pair of graph morphisms (α,α˜) whereα: X1→ X2and ˜α: ˜X1→ X˜2such thatα℘1=℘2α˜. Note that if ˜αis a covering projection then so isα, and ifαis a covering projection then so is ˜αprovided that ˜αis onto. The definitions ofepi-, mono-, iso- andautomorphismsof covering projections follow directly from the categorical definitions and are self-explanatory. In particular, two covering projections℘1and℘2 areequivalent if there exists an isomorphism of the form (id, φ).
Thegroup of covering transformationsCT(℘) of℘: ˜X → X is the group of all self- equivalences of℘, that is, of all automorphismsτ ∈Aut ˜X such that℘τ=℘. Since ˜Xis assumed to be connected the group CT(℘) acts semiregularly on each vertex- and dart-fibre.
If CT(℘) acts transitively (and hence regularly) on each fibre, then the covering projection
℘is calledregular. In this case the orbits of CT(℘) coincide with the fibres of℘, and℘is isomorphic to the quotient projection pCT(℘): ˜X → X˜CT(℘). Moreover, ifX is a connected graph andN ≤AutX acts regularly on each of its vetex- and dart-orbits, then the quotient projectionpN: X→ XN is a regular covering projection withNas the group of covering transformations. An equivalent characterization of a regular covering projection in terms of fundamental groups is the following. Consider the monomorphismπ( ˜X,b)˜ →π(X,b) induced by℘, where ˜b ∈ ℘−1(b). Then℘is regular if and only if the image ofπ( ˜X,b)˜ under this monomorphism is a normal subgroup ofπ(X,b).
2.3. Voltages
Regular covering projections can be grasped combinatorially as follows [11, 18]. ACayley voltage spaceon a connected graphX =(D,V; beg,inv) is an ordered pair (N;ζ), where N is avoltage groupacting on itself by right multiplication, andζ: D→ N is a function such thatζ(x−1)=(ζ(x))−1. The valueζ(x) is called thevoltageof the dartx ∈ D. This function extends naturally to all walks. Note that homotopic walks have the same voltage and thatζ : π(X,b) → N is a group homomorphism. Conversely, any homomorphism π(X,b) → N ‘extends’ to a voltage space on X by assigning to the darts of a spanning tree the trivial voltage, and to the cotree darts the images of the corresponding generators ofπ(X,b) under this homomorphism. The voltage space is calledlocally transitiveif the homomorphismζ :π(X,b)→N is onto.
Let (N;ζ) be a locally transitive Cayley voltage space on a connected graph X = (D,V; beg,inv). With (N;ζ) weassociateaderived covering projection℘ζ: Cov(N;ζ)→
Xas follows. The graph Cov(N;ζ) hasD×NandV×Nas the sets of darts and vertices, respectively, with beg(x, ν)=(begx, ν) and inv(x, ν)=(invx, νζ(x)). The corresponding projection℘ζ is defined as the projection onto the first component. This is indeed a regular covering projection with CT(℘ζ)∼=N. Namely, for eacha∈ Ndefine a covering transfor- mationλabyλa(x, ν)=(x,aν) (x∈ DX∪VX). The mappingλ: N →CT(℘ζ) establishes an isomorphism of the left regular action ofNon itself and the action of CT(℘ζ) on a fibre.
The kernel of the homomorphismζ:π(X,b)→ Nis precisely the image ofπ( ˜X,b) under˜ the monomorphismπ( ˜X,b)˜ →π(X,b) induced by℘. Conversely, with any regular cov- ering projection℘: ˜X → X there is anassociatedlocally transitive Cayley voltage space (N;ζ) on X withN ∼= CT(℘) such that the derived covering projection℘ζ is equivalent to℘; the required (N;ζ) is obtained as follows. First, for each dartx ∈ DX choose a dart
˜
x1 ∈ fib(x) and label ˜x1 and its initial vertex by lab( ˜x1) = lab(beg ˜x1) = 1 ∈ N. The extension of this labelling toDX˜ andVV˜ obtained by using the left action of CT(℘) satisfies the equality lab( ˜x)·lab(inv ˜x1) =lab(inv ˜x) for all dartsx ∈ DX and ˜x ∈ fib(x). Thus, we set the voltage of the dartx∈ DX to be the label of inv ˜x1, that is,ζ(x)=lab(inv ˜x1).
Moreover, by taking an arbitrary spanning treeT inXand labelling the vertices of a con- nected component of℘−1(T) in ˜X by 1, we obtain a voltage space with the trivial voltage assigned to darts ofT.
For all group and graph theoretic concepts not defined above we refer the reader to [10, 11, 14, 18].
3. Lifting and projecting automorphisms
Let℘: ˜X → X be a covering projection. If (α,α˜) is an automorphism of℘we say that α˜ is aliftofαand thatαis aprojectionof ˜α. Observe thatαis uniquely determined by α, but ˜˜ αis in general not uniquely determined byα. It is true, however, that ˜αis uniquely determined by the image of a single vertex (or dart). The set of all lifts of a givenα∈AutX is denoted byL(α). Clearly,L(id)=CT(℘). More generally, letG ≤ AutX. If for each α ∈Gthe set of liftsL(α) is nonempty, then ˜G = ∪α∈GL(α) is a group called theliftof G. The induced group homomorphism℘G˜: ˜G → Ghas CT(℘) as the kernel and hence the sequence CT(℘) → G˜ → Gis short exact. We also say thatG is aprojectionof ˜G (although there may exist a proper subgroup of ˜Gwhich projects toG).
In what follows we restrict to the case when the covering projection℘: ˜X → Xis regular.
Then the largest subgroup of Aut ˜Xthat projects is precisely the normalizer of CT(℘) within Aut ˜X. The question whether a given subgroupG≤AutX lifts can be answered in terms of an associated Cayley voltage space (N, ζ) as follows [18].
Proposition 3.1 Let(N;ζ)be a Cayley voltage space associated with a regular covering projection℘: ˜X → X . Then a group G ≤AutX lifts if and only if for eachα∈G there exists a group automorphismα#b ∈AutN such that
α#bζ =ζα,
whereζis considered as a homomorphism defined onπ(X,b)andπ(X, α(b)), respectively.
It should be noted that α#b ∈ AutN depends on the base vertex b ∈ VX, and that
#b:G→AutNis not a group homomorphism in general. The situation changes drastically if we assume that the group of covering transformations is abelian. We postpone further discussion on this until Section 5.
Later on we shall need a more general version of Proposition 3.1. This is gathered in the next theorem and its corollary below.
Theorem 3.2 Let(Ni;ζi) (i =1,2)be two Cayley voltage spaces associated with regular covering projections℘i: ˜Xi → X(i = 1,2),respectively,and letα ∈ AutX . Then the following statements are equivalent.
(a) There exists an epimorphism(α,α) :˜ ℘1→℘2.
(b) There exists a group epimorphismτ: N1→ N2such thatτζ1=ζ2α,whereζ1is consid- ered as a homomorphismπ(X,b)→ N1andζ2as a homomorphismπ(X, α(b))→N2. Moreover,the epimorphism(α,α)˜ from the statement(a)is an isomorphism if and only if the epimorphismτ from statement(b)is an isomorphism.
Proof: We may assume that℘i (i =1,2) are actually the derived covering projections.
Suppose first that (a) holds. Take a closed walkW atb∈ VX such thatζ1(W)=1. Its lift
℘1−1(W) is a disjoint union of closed walks isomorphic toW. Sinceα℘1=℘2α˜, the image α˜(℘−11(W)) is a lift ofα(W), and hence also a disjoint union of closed walks. Since ˜αis a graph morphism, the cycles in ˜α(℘1−1(W)) have length at most that ofW. On the other hand, being the lifts ofα(W)∼=W, their length is at least that ofW. Hence,α(W) lifts to a disjoint union of closed walks isomorphic toα(W), implying thatζ2(α(W))=1. Thus, α(Kerζ1)≤Kerζ2, and (b) follows.
Suppose now that (b) holds. We first explicitly define the required epimorphism ˜αon darts of Cov(N1, ζ1). Let (x, ν) be an arbitrary dart of Cov(N1, ζ1), wherexis a dart of X andν∈N1. Define
α(x, ν)˜ =(α(x), τ(ν)ζ2(α(W))),
whereWis an arbitrary walk from the base vertexbto begxwith voltageζ1(W)=1. (Note that such a walk always exists sinceζ1:π(X,b)→ N1is onto.) First of all, the mapping is well defined. Namely, letW andWbe two such walks. ThenW−1Wis a closed walk atb with trivialζ1-voltage. In view of the fact thatζ2α=τζ1the walkα(W−1W) has trivial ζ2-voltage. Thus,ζ2(α(W))=ζ2(α(W)), and hence ˜αis well defined. In order to see that it commutes with inv, observe that
α(inv(x, ν˜ ))=(α(x−1), τ(ν)τ(ζ1(x))ζ2(α(W))),
whereWis a walk frombto begx−1with trivialζ1-voltage. On the other hand, inv ˜α(x, ν)=(α(x)−1, τ(ν)ζ2(α(W))ζ2(α(x))).
Let us now consider the closed walk Wx−1W−1 at b. We have ζ2α(Wx−1W−1) = τζ1(Wx−1W−1). Using the fact thatζ1(W)=ζ1(W)=1, a short calculation now shows that ˜αindeed commutes with inv.
Finally, ˜αcan obviously be extended to vertices such that ˜αis indeed a graph epimorphism satisfyingα℘1 =℘2α.˜
The last part of the theorem is clear from the constructions of ˜αandτ. Corollary 3.3 Let(Ni;ζi) (i =1,2)be two locally transitive Cayley voltage spaces on a connected graph X . Then the derived regular covering projections℘1and℘2are
(a) isomorphic if and only if there exists a group isomorphismτ : N1→ N2andα∈AutX such thatτζ1=ζ2α,whereζ1andζ2are considered as homomorphismsζ1:π(X,b)→ N1andζ2:π(X, α(b))→N2;
(b) equivalent(cf. [23, Theorem 2])if and only if there exists an isomorphismτ: N1 →N2
such thatτζ1 = ζ2,where ζ1 and ζ2 are considered as homomorphisms defined on π(X,b).
4. Ordering admissible regular coverings
In this section we revise some results of Venkatesh [24, 25], tailored to our present needs and giving somewhat different proofs.
LetX be a connected graph andG≤AutX. A regular covering projection℘: ˜X → X is called G-admissible if G lifts along ℘. If ℘i: ˜Xi → X (i = 1,2) are regular G- admissible covering projections, define℘2 ≤℘1if and only if there exists an epimorphism (id, α) :℘1 →℘2. Clearly,℘1and℘2are equivalent if and only if℘1 ≤℘2and℘2 ≤℘1. Therefore, the ordering≤induces a partial ordering on the setCG(X) of equivalence classes ofG-admissible regular covering projections ontoX. This ordering, which is in fact a lattice, is denoted by the same symbol≤. The interval{[℘]|[℘]≤[℘]} ⊆CG(X)}is denoted by CG(℘).
Let℘: ˜X →X be a regular covering projection. IfK ≤CT(℘), then℘factors through the regular covering projection℘K: ˜X → X˜K. The corresponding covering projection X˜K → X maps according to the rule K x → ℘(x), where K x is a dart (or vertex) of X˜K, that is, the orbit of a dart (or vertex)xof ˜X under the action ofK. IfK is normal in N =CT(℘) we denote this covering projection by
℘N/K: ˜XK → X.
SinceK is normal inN, the groupNprojects along℘K to a group isomorphic withN/K. Because℘=℘N/K℘K, this projected group is contained in CT(℘N/K) and, moreover, it is transitive on each of the fibres of℘N/K. Thus,℘N/K is regular with CT(℘N/K) isomorphic to N/K. If℘ is G-admissible with ˜G being the lift of G, let NG(℘) denote the set of subgroups of CT(℘) which are normal in ˜G.
Proposition 4.1 Let(N, ζ)be the Cayley voltage space associated with a G-admissible regular covering projection℘: ˜X → X,and letG be the lift of G˜ ≤AutX . Suppose that K ∈NG(℘). Then:
(a) The covering projection℘N/K: ˜XK → X is regular G-admissible,with the lift of G isomorphic to the quotient groupG/K˜ ,and℘N/K ≤℘;
(b) The covering projection℘N/K is equivalent to the derived covering projection℘qζ: Cov(N/K,qζ)→X,where q: N → N/K is the natural quotient projection.
Proof: By the remarks above we already know that℘N/K is regular. SinceK is normal in ˜G, the group ˜Gprojects along℘K onto a group isomorphic with ˜G/K. Since N/K is normal in ˜G/K, the latter projects along℘N/K. Let ˜g ∈G˜ be a lift ofg ∈Galong℘, and let ¯gbe the projection of ˜galong℘K, that is, letg℘ =℘g˜and ¯g℘K =℘Kg. Then we have˜ g℘N/K℘K =℘N/K℘Kg˜ =℘N/Kg℘¯ K, and consequently,g℘N/K =℘N/Kg. Hence¯ ℘N/K
isG-admissible and℘N/K ≤℘. This proves (a).
In order to prove (b) we can assume that ˜X = Cov(N, ζ) and that ℘ is the derived covering projection. The vertices and darts of the graph ˜XK are then the orbits K(x, ν), wherexis a vertex or a dart ofXandν∈N. Define the mappingα: ˜XK →Cov(N/K;qζ) byK(x, ν)→(x,Kν). This is clearly a well defined graph isomorphism satisfying℘N/K =
℘qζα.
The assignmentK → [℘N/K], where K and℘N/K are as in Proposition 4.1, gives rise to a mapping
(G,℘): NG(℘)→CG(℘).
We shall prove that(G,℘)is an order reversing bijection (relative to the inclusion-order in NG(℘) and the order≤inCG(℘)), see Theorem 4.4 below. The bijective correspondence betweenNG(℘) andCG(℘) was essentially established in [24, 25], using a somewhat differ- ent approach. Theorem 4.4 is a direct consequence of Propositions 4.2 and 4.3 below. The first of these says that the mapping(G,℘) is order reversing and mono, while the second one says that(G,℘)is onto.
Proposition 4.2 Let ℘: ˜X → X be a G-admissible regular covering projection. Let K1,K2∈NG(℘)and let N =CT(℘). Then[℘N/K1]≤[℘N/K2]if and only if K2≤ K1. In particular, ℘N/K1and℘N/K2are equivalent if and only if K1=K2.
Proof: Let (N, ζ) be a Cayley voltage space associated with℘. By Proposition 4.1℘N/Ki
(i = 1,2) is equivalent to the derived covering projection℘qiζ: Cov(N/Ki,qiζ) → X, whereqi: N → N/Kiis the natural quotient projection.
Since℘N/Ki (i =1,2) are bothG-admissible, we have that [℘N/K1]≤[℘N/K2] holds if and only if there exists an epimorphism (id, α) :℘q2ζ →℘q1ζ. The condition is equivalent, by Theorem 3.2, to the requirement that there is a group epimorphismτ: N/K2→ N/K1
such thatτq2ζ =q1ζ. But this is equivalent toτq2=q1(sinceζ is onto), which is nothing butK2=Kerq2 ≤Kerq1=K1. The last statement in the proposition is now evident.
Proposition 4.3 Let ℘: ˜X → X and q: Y → X be G-admissible regular covering projections, where q ≤ ℘. Then there exists a subgroup K ∈ NG(℘) such that q is equivalent to the covering projection℘N/K,where N =CT(℘).
Proof: By definition there exists a graph epimorphismα: ˜X → Y such that℘ = qα.
Clearly,αis a covering projection. Consider the monomorphic projections of the funda- mental groups of ˜X andY to corresponding subgroups PandQinπ(X,b), respectively.
Since℘ factors throughq we have P ≤ Q. As℘ is regular,P is normal inπ(X,b) and hence in Q. Thus, the covering projectionαis regular, too. It follows that there exists an isomorphism of covering projections (ι,id) : ℘K →α, whereK =CT(α). Since℘=qα we haveK ≤ N =CT(℘). Now let ¯G≤AutY be the lift ofGalongqand let ˜G≤Aut ˜X be the lift ofG along ℘. We leave to the reader to show that ¯G must lift alongαto ˜G (see [?, Lemma 4.1.3]). This is equivalent to saying that ˜G projects along℘K, or, that K ∈NG(℘). Finally, from℘N/K℘K =℘ =qα=qι℘K we conclude that℘N/K =qι. In other words,q is equivalent to℘N/K: ˜XK → X. (An alternative proof of this proposition
using Theorem 3.2 is left to the reader.)
Theorem 4.4 The mapping(G,℘): NG(℘)→CG(℘)is an anti-isomorphism of lattices (NG(℘),⊆)and(CG(℘),≤).
Let ℘: ˜X → X be a G-admissible regular covering projection. Observe that CG(℘) contains at least two equivalence classes, namely the one induced by the identity projection idX: X → X and the one induced by℘. If these are the only elements ofCG(℘) then℘ is called minimal G-admissible regular covering projection [24, 25]. It is clear that any G-admissible regular covering can be decomposed into a series of minimal ones. Such coverings can be characterized by a certain maximality condition imposed on the normal subgroups of π(X,b) which determine these coverings up to equivalence [24, 25]. An equivalent characterization is the following.
Corollary 4.5 Let℘: ˜X → X be a G-admissible regular covering projection. Then℘is minimal if and only ifCT(℘)is a minimal normal subgroup of the lifted groupG.˜
Proof: By definition,℘ is minimal if and only if the setCG(℘) consists of at most two elements. This is equivalent, by Theorem 4, to saying that the setNG(℘) has at most two elements. But this is equivalent to saying that CT(℘) is a minimal normal subgroup of ˜G.
We end this section by a more general analogue of Proposition 4.2. We give a criterion for the covering projections℘N/K1and℘N/K2to be isomorphic. See Sections 6 and 7 for an application.
Proposition 4.6 Let℘ : ˜X → X be an(AutX)-admissible regular covering projection.
Suppose that K1 and K2 are two normal subgroups of N = CT(℘). Then the induced covering projections℘N/K1: ˜XK1→ X and℘N/K2: ˜XK2→ X are isomorphic if and only if there exists an automorphismα∈AutX such thatα#b(K1)=K2.
Proof: Let (N, ζ) be a Cayley voltage space associated with ℘. By Proposition 4.1, the covering projection ℘N/Ki (i = 1,2) is associated with the Cayley voltage space (N/Ki,qiζ), whereqi: N → N/Ki is the quotient homomorphism. By Corollary 3.3,
the derived covering projections℘q1ζ and℘q2ζ are isomorphic if and only if there exists an isomorphism of groupsτ: N/K1→N/K2and a graph automorphismα∈AutXsuch that τq1ζ =q2ζα. Sinceαlifts along℘, Proposition 3.1 implies that there is an automorphism α#b∈AutNsatisfyingζα=α#bζ. Asζ is onto, we deduce thatτq1ζ =q2ζα=q2α#bζis equivalent toq2α#b =τq1. The existence ofτis equivalent to the fact thatα#bmaps Kerq1
to Kerq2, that is,α#b(K1)=K2.
5. Abelian regular covers
A regular covering projection℘: ˜X → X isabelianif the group CT(℘) is abelian. Let (N;ζ) be a Cayley voltage space associated with such a covering. Observe that the homo- morphismζ: π(X,b) → N now factors through the abelianizationπ(X,b) → H1(X).
The corresponding homomorphismH1(X)→ N(a linear mapping ofZ-modules) will also be denoted byζ. Converesely, any epimorphismH1(X)→ N‘extends’ to an epimorphism π(X,b)→ Nwhich in turn gives rise to an abelian regular covering projection. We express this informally by saying that the voltage assignment can be taken as defined on the first homology group.
This fact has considerable impact on our treatement of lifting automorphisms. First, we restate Proposition 3.1, omitting the obvious proof. A similar restatement of Theorem 3.2 and of Corollary 3.3 is left to the reader.
Proposition 5.1 Let(N;ζ)be a Cayley voltage space associated with an abelian regular covering projection℘: ˜X →X . Then a group G≤AutX lifts if and only if for eachα∈G there exists a group automorphismα#∈AutN such that
α#ζ =ζα,
whereζ andαare considered as defined on H1(X). In particular,if G lifts then for each α∈G the automorphismα#bof Proposition 3.1 does not depend on the base vertex b, and considered as defined on H1(X)it conicides withα#.
Proposition 5.1 can be further rephrased by saying that the groupG≤AutXlifts along℘ζ
if and only if Kerζ is an invariant submodule of the naturally defined linear representation of G on the Z-module H1(X). This readily implies that the (equivalence classes of) G- admissible abelian regular covering projections of X are in bijective correspondence with theG-invariant submodules of finite index inH1(X).
To put the above into a wider setting, recall the anti-isomorphism of lattices(G,℘): NG(℘) → CG(℘) defined in Section 4. We are now going to show, first, that there is a nice combinatorial characterization of NG(℘) in terms of voltages, and second, that this characterization is intimately related with the lifted groups considered as extensions of the group of covering transformations. Suppose that a subgroup G ≤ AutX has a lift. The coupling of the extension CT(℘) → G˜ → G with abelian kernel is a homomorphism : G → Aut CT(℘),α → α, defined relative to (and independent of) an algebraic transversal{α¯ ∈ L(α)|α ∈ G}(with ¯id= id), whereαis given byα: c→ αc¯ α¯−1.
A general discussion on the coupling of the extension CT(℘) → G˜ → G in terms of fundamental groups can be be found in [24, 25].
Theorem 5.2 Let(N;ζ)be a locally transitive Cayley voltage space on a connected graph X,with N abelian,and let℘be the derived covering projection. Suppose that G≤AutX has a lift. Then:
(a) The induced mapping# :G→AutN is a group homomorphism.
(b) The coupling for the extensionCT(℘) → G˜ → G is =λ#,ˆ whereλˆ: AutN → Aut CT(℘) is the isomorphismφ → λφλ−1 (induced by the isomorphismλ: N → CT(℘)which assigns to each a∈ N the covering transformationλa).In particular,if we identify N =CT(℘) (viaλ)thenα#(ν)=αν˜ α˜−1,for eachα∈ G,α˜ ∈L(α)and ν∈ N .
Proof: Letα, β ∈ AutX, and let C be an arbitrary closed walk in X. Then we have α#β#(ζ(C))=α#(ζ(β(C)))=ζ(αβ(C))=(αβ)#(ζ(C)), and (a) holds.
In order to prove (b), recall that the action of CT(℘) on an arbitrary dart or vertex (x, ν) of Cov(N;ζ) is given byλa(x, ν)=(x,aν), and observe that
α˜(x, ν)=(α(x), τxα#(ν))
for an appropriate τx ∈ N dependent on x and α. We have ˜αλa(x, ν) = α˜(x,aν) = (α(x), τxα#(ν))=(α(x), τxα#(a)α#(ν))=(α(x), α#(a)τxα#(ν))=λα#(a)(α(x), τxα#(ν))= λα#(a)α(x, ν˜ ). Thus, ˜αλaα˜−1 =λα#(a). It follows that (αλ)(a) =(λα#)(a) for alla ∈ N. Hence(α)=α=λα#λ−1=( ˆλ#)(α) for allα∈G. The rest is obvious.
By part (a) of Theorem 5.2 we can view the mapping # : G → AutN as a linear rep- resentation of the groupGover theZ-moduleN. Let Inv(#) denote the set of #-invariant submodules of this representation. Then part (b) of Theorem 5.2 implies the following corollary.
Corollary 5.3 If we identify N =CT(℘)(viaλ) as in Theorem5.2thenInv(#)=NG(℘).
In view of the above identification we shall consider the mapping(G,℘)as defined on the set Inv(#).
As a final remark, consider thehomological covering: ˜X→ Xwhich is characterized by the fact that CT() is isomorphic to the first homology groupH1(X). Note that the graph X˜is infinite and observe that all theorems and propositions stated so far are valid in the infinite case as well. It easily follows that there is, up to equivalence, only one such covering obtained by takingζ: H1(X)→ H1(X) to be the identity mapping. Also, this covering is (AutX)-admissible. Using Theorem 5.2 we can find all equivalence classes of (finite)G- admissible abelian regular covering projections ofX via the linear representation ofGon H1(X), as already mentioned in the paragraph following Proposition 5.1. We shall take a closer look at this in the next section when discussingp-homological covers.
6. Elementary abelian regular covers
We start this section with some remarks regarding notation and terminology. By n we denote the standard basis of the (column!) vector spaceFnover a fieldF. IfA:U→W is a linear mapping between twoF-vector spacesUandWof finite dimension, then [A;BW,BU] denotes the corresponding matrix relative to the basesBUandBWforUandW, respectively.
IfM ∈Fm×n is a matrix then the same symbol denotes the corresponding linear mapping Fn → Fm, that is, M = [M;m, n]. ByU∗ we denote the dual of anF-vector space U, and byB∗ its dual basis relative to a basisBofU. The dual of a linear transformation A:U→Uis denoted byA∗. ForK ≤Uletω(K)= {f ∈U∗| f(K)=0} ≤U∗denote theannihilatorofK.
Ifφ:G→AutUis a linear representation of a groupG, then the compositionφ∗= ∗φ is a linear anti-representation ofGonU∗. By Inv(φ) and Inv(φ∗) we denote the set of allφ- andφ∗-invariant subspaces of these representations, respectively. Observe thatωinduces the anti-isomorphism of latticesωφ: Inv(φ)→Inv(φ∗).
Lemma 6.1 LetB= {e1,e2, . . . ,ed}be a basis of a vector space U andB∗= {e∗1,e∗2, . . . , e∗d}the dual basis of U∗. For arbitrary bases{b1,b2, . . . ,bk}and{f1∗, f2∗, . . . , fd∗−k}of subspaces K ≤U and M≤U∗,respectively,let
Q=[fi∗(ej)]ij==11,... ,,... ,dd−k∈F(d−k)×d and B=[ei∗(bj)]ij==11,... ,,... ,dk∈Fd×k. Then M =ω(K)if and only if Q B=0∈F(d−k)×k.
Proof: It suffices to observe that the (s,t)th-element [Q B]s,tof the matrixQ Bis [Q B]s,t =
d j=1
fs∗(ej)e∗j(bt)= d
j=1
fs∗(ej)e∗j
(bt)= fs∗(bt).
From now on we restrict our considerations to finite dimensional vector spaces over an arbitrary prime field Zp, and are ready to consider the main topic of this section: If X is a given connected graph and G ≤ AutX a given subgroup of automorphisms, find all G-admissible regular covering projections℘: ˜X → X, up to equivalence (or possibly, up to isomorphism) of covering projections. This is almost intractable in general. A restricted subproblem would be to findCG(℘0), where℘0is some knownG-admissible covering. In view of Theorem 4.4 we first find the setNG(℘0) (which could be difficult), and then use part (b) of Proposition 4.1 to construct the corresponding coverings(G,℘0)(K) (K ∈NG(℘0)).
However, finding the corresponding voltage assignments explicitly—that is, using a suitable predefined presentation of the ‘abstract’ group CT(℘0)/K—may again not be easy. The situation changes if we restrict to consider elementary abelian covers, which we now define.
A regular covering projection℘: ˜X → Xis calledelementary abelianif the group CT(℘) is elementary abelian. If (N;ζ) is an associated Cayley voltage space we shall sometimes regard the elementary abelianp-groupNas aZ-module or as the additive group of a vector space overZp. (Hereafter,N will always denote an elementary abelianp-group.)
As mentioned in Section 5, the commutativity of N enables us to consider the voltage assignment as a linear mapping ofZ-modulesζ: H1(X) → N. Now even more holds.
Since the groupNis of exponentp, the kernel Kerζcontains the submodulep H1(X), and ζ factors through the moduleH1(X;Zp). The induced linear mappingH1(X;Zp)→N of vector spaces overZpwill still be denoted byζ. Conversely, any such mapping ‘extends’ to a mapping defined onπ(X,b), and this defines an appropriate elementary abelian covering.
Informally we say that the voltage assignment ζ can be viewed as defined on the first homology groupH1(X;Zp). Also, we leave to the reader to formally adapt all the theorems, propositions and corollaries stated thus far to fit into this context.
Now let℘: ˜X → Xbe aG-admissible elementary abelian regular covering projection, and let (N;ζ) be an associated Cayley voltage space withN ∼=Zdp, whereζis considered as aZp-linear mapping defined onH1(X;Zp). As usual, # : G→AutN is the corresponding linear representation and(G,℘): Inv(#) → CG(℘) the anti-isomorphism of lattices. We define(G∗,℘): Inv(#∗)→CG(℘) as(G∗,℘) =(G,℘)ω−#1, whereω#: Inv(#)→Inv(#∗) is as above. Observe that(G∗ ,℘)is now a lattice isomorphism.
Theorem 6.2 With the notation and assumptions above, letϕ: H1(X,Zp)→Zrp be the isomorphism mapping a chosen basisCtor, and let Z=[ζ;d,C].
(a) LetBK = {b1,b2, . . . ,bk}be a basis for K ∈Inv(#),and let B∈Zdp×kbe the matrix with columns b1,b2, . . . ,bk. If Q ∈ Z(dp−k)×d is a matrix of rank d−k satisfying Q B =0 ∈ Z(dp−k)×k,then℘N/K =(G,℘)(K)is associated with the Cayley voltage space(Zdp−k;Q Zϕ).
(b) Letd = {e1,e2, . . . ,ed}be the standard basis for N =Zdp,and letBM = {f1∗, f2∗ , . . . , fm∗}be a basis for M∈Inv(#∗). Define
Q=[fi∗(ej)]ij==11,... ,,... ,md ∈Zmp×d.
Then(G∗ ,℘)(M)is associated with the Cayley voltage space(Zmp;Q Zϕ).
Proof: We first prove (a). By Proposition 4.1 we can assume that ˜XK =Cov(N/K,qζ) and that℘N/K is the derived covering projection℘qζ: Cov(N/K,qζ)→ X. Consider the matricesBandQas linear mappingsZkp
−→B Zdp
−→Q Zdp−k. Observe thatK =ImB. For an arbitrary elementx+K ∈ N/K defineτ(x+K)= Qx. Since Qx =0 forx ∈ K, the mappingτ: N/K → Zdp−kis an isomorphism satisfyingτq = Q. Observe thatZϕ =ζ. Thus,τqζ =Q Zϕ, and (a) follows by Corollary 3.3.
We now prove (b). Let{b1,b2, . . . ,bd−m}be a basis forK=ω−1(M) and{e∗1,e∗2, . . . ,e∗d} the dual basis ofd. DefineB =[e∗i(bj)]ij==11,... ,,... ,dd−m ∈Zdp×(d−m). By Lemma 6.1 we have Q B=0, and by part (a) of this theorem,(G∗ ,℘)(M)=℘N/Kis associated with (Zmp,Q Zϕ).
Remark In practice, the rows of the matrix Qin (a) of Theorem 6.2 are computed by solving the system of linear equationsBtx =0.
As for part (b), theith row of the matrix Qcomprises the components of fi∗relative to the dual basisd∗. Hence the rows ofQcan be computed by finding a basis of an invariant
