ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 83-94
Reachability relations, transitive digraphs and
groups
Aleksander Malnic *
University of Ljubljana, Faculty of Education, Kardeljeva pl. 16, 1000 Ljubljana, Slovenia
IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Primož Potočnik
University ofLjubljana, Faculty ofMathematics and Physics Jadranska 19, 1000 Ljubljana, Slovenia IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia
Norbert Seifterf
Montanuniversität Leoben, Franz-Josef-Strasse 18, A-8700 Leoben, Austria
Primož Sparl *
University of Ljubljana, Faculty of Education, Kardeljeva pl. 16, 1000 Ljubljana, Slovenia Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Received 28 August 2013, accepted 9 March 2014, published online 7 May 2014
In [6] it was shown that properties of digraphs such as growth, property Z, and number of ends are reflected by the properties of certain reachability relations defined on the vertices of the corresponding digraphs.
In this paper we study these relations in connection with certain properties of automorphism groups of transitive digraphs. In particular, one of the main results shows that if a transitive digraph admits a nilpotent subgroup of automorphisms with finitely many orbits, then its nilpotency class and the number of orbits are closely related to particular properties of reachability relations defined on the digraphs in question.
The obtained results have interesting implications for Cayley digraphs of certain types of groups such as torsion-free groups of polynomial growth.
* Supported in part by "ARRS - Agencija za znanost Republike Slovenije", program no. P1-0285. t Corresponding author. Supported by ÖAD - WTZ (Österreich-Slowenien, project no. SI 20/2009. i Supported in part by "ARRS - Agencija za znanost Republike Slovenije", program no. P1-0285.
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
84
Ars Math. Contemp. 8 (2015) 149-162
Keywords: Cayley digraph, reachability relation. Math. Subj. Class.: 05C20, 05C25
1 Introduction and preliminaries
In [2], highly arc-transitive digraphs were considered from several different viewpoints, leading to - besides many nice results - a number of interesting problems. One of these problems, which remained open for a very long time and was finally settled in [4], concerned a certain reachability relation defined on the edges of digraphs. A subset of the authors of this paper also worked on this 'reachability problem' [5] and several other questions concerning highly-arc-transitive digraphs. In [6], as an offspring of our considerations, we became interested in reachability relations defined on vertices rather than edges, which we review in the sequel.
A digraph is an ordered pair D = (V(D), E(D)), where V(D) is the vertex-set and E(D) C V(D) x V(D) is the edge-set. Note that a digraph can have loops (v, v) as well as pairs of 'oppositely directed' edges of the form (u, v) and (v, u). We also emphasize that with this definition our digraphs are always simple in the sense that between two vertices there can be at most one edge in each direction. Digraphs considered in this paper are connected in the sense that their underlying undirected graphs are connected.
By Aut(D) we denote the automorphism group of a digraph D. We say that D is transitive if some H C Aut(D) acts transitively on the vertices of D. Also, if g G Aut(D), then gv denotes the image of v G V(D) under g and Hv denotes the orbit of v under some subset H C Aut(D).
To make sure that no ambiguity arises, we explicitely define Cayley digraphs as they are understood in this paper. The Cayley digraph Cay(G, S) of a group G with respect to a generating set S has the group G as its vertex set and the edges are given by right multiplication by the generators: E(Cay(G, S)) = {(g, gs)|s G S}. If Cay(G, S) is defined in this way, then G acts regularly on Cay(G, S) by left multiplication.
A walk W = (v0, £i, vi,..., £n, vn) from v0 to vn of length n > 0 (denoted by | W|) is a sequence of n +1 (not necessarily pairwise distinct) vertices v0, v1,..., vn G V(D), and n indicators e1, e2,..., e„ G {1, -1} such that for all j G {1,2,..., n} we have
£j = 1 ^ (vj-i,vj) G E(W), £j = -1 ^ (vj,vj-i) G E(W).
W is called a closed walk if v0 = vn. Intuitively, a walk is a traversal in the digraph from vertex to vertex along edges, where indicators 1 and -1 tell whether the traversal respects the direction of edges or not. The formal definition of a walk as above has been chosen in order to make proofs unambiguous. If the vertices of a walk W are pairwise different then W is called a path. A walk (or a path) is directed if its indicators are all equal to 1 or to -1, and is alternating if the values of the indicators alternate.
Let W = (v0, £1, v1,..., e„, vn) be a walk. We let the inverse walk of W be W-1 = (vn, -£„, vn-1,..., —£1, v0). Moreover, for 0 < i < j < n, the subsequence
iWj = (vj,£i+1, . . . ,£j, vj)
E-mail addresses: aleksander.malnic@pef.uni-lj.si (Aleksander Malnic), primoz.potocnik@fmf.uni-lj.si (Primož Potočnik), seifter@unileoben.ac.at (Norbert Seifter), primoz.sparl@pef.uni-lj.si (Primož Sparl)
A. Mainte: et al.: Reachability relations, transitive digraphs and groups
85
of W is called a subwalk. Furthermore, let W' = (u0, u^ ..., ¿m, um) be a walk such that u0 = vn. Then the concatenation of W and W' is the walk
W • W' = (vo, £1, Vi, . . . , Vn-1, £n, «0, ¿1, «1, ... , ¿m, Um)
of length n + m.
We now introduce two families of reachability relations defined on vertices of a digraph.
Let W = (v0, £1, v1,..., £n, vn) be a walk. The weight of the walk W is defined as
Z (W) = £1 + £2 + ... + £„.
Let k be a nonnegative integer. We say that a vertex « g V(D) is R+-related to a vertex v g V(D), in symbols
uR+v,
if there exists a walk W from u to v such that Z(W) = 0, and that for every 0 < j < |W| we have Z(0Wj) g [0, k]. For a given pair of vertices u, v, the set of all such walks is denoted by R+[u, v]. Analogously we say that u is R--related to v, in symbols wR-v, if there exists a walk W such that Z(W) = 0, and that for every 0 < j < |W| we have Z(0Wj) g [—k, 0]. For a given pair of vertices u, v, the set of all such walks is denoted by R- [u, v]. Note that R+ and R- are equivalence relations. Their equivalence classes are denoted by R+(v) and R-(v), v g V(D), respectively. If D is transitive, then the equivalence classes of R+ (and similarly of R-) form an imprimitivity system for Aut(D). Observe that the sequences (R+)fceZ+ and (R-)fceZ+ are ascending: for all k we have R+ C R++1 and R- C R-+1. Their respective unions
R+ = U R+ and R- = U Rfc
hez+	hez+
are thus also equivalence relations, and their equivalence classes form imprimitivity systems for Aut(D) whenever D is transitive. As was shown in [6], R+ = R+ holds whenever R+ = R++i. In this case, the smallest nonnegative integer k such that R+ = R+ holds is called the exponent exp+(D) of D. If R+ = R+ for all k, then we set exp+(D) = to. The exponent exp-(D) is defined analogously. We say that the relation R+ (R+, R-, R-) is universal if uR+v (uR+v, uR-v, uR-v) holds for any pair u, v G V(D). We mention (see [6]) that all of the above relations are universal, provided that the digraph in question is connected and has a loop at every vertex.
In [6] it was also shown that properties of the two sequences of equivalence relations (R+)fceZ+ and (R-)fceZ+ are strongly related to other properties of digraphs such as having property Z, the number of ends, growth conditions and vertex degree.
Furthermore, in [8] the relations Ra,b were studied, where a is a non-positive integer or a = -to and b is a non-negative integer or b = to. We say that a vertex u is Ra,b-related to a vertex v if there exists a 0-weighted walk from u to v such that every subwalk starting at u has weight in the interval [a, b].
The distance distD (u, v) between vertices u and v in a connected digraph D is the length of a shortest path from u to v in the underlying undirected graph. The growth function fD(v, n), n > 0, with respect to some v G V(D) is given by
fD(v,n) = |{u G V(D) | distD(v,u) < n}|.
86
Ars Math. Contemp. 8 (2015) 149-162
If D is transitive, then this function does not depend on a particular vertex v e V(D). In this case we denote it by fD (n).
We say that a transitive digraph D has polynomial growth if there are positive constants c and d such that
fD (n) < cnd
holds for all n > 0. The digraph D has exponential growth if there is a constant c > 1 such that
fD (n) > cn
holds for all n > 0. If the growth function of a digraph D grows faster than any polynomial but D does not have exponential growth, then we say that D has intermediate growth. In the case of polynomial growth it can be shown that there always exist constants ci, c2 and an integer d > 1 such that
ci nd < fD (n) < C2nd
holds for all n > 0. We call this integer d the growth degree of D. We remark that the definitions concerning growth coincide with the usual definitions in the context of undirected graphs.
Let D be a digraph and let t be a partition of the vertex set of D. The quotient digraph Dt of D with respect to t is the digraph with vertex set t and (uT, vT) e E(D) if and only if there exist vertices u e uT and v e vT such that (u, v) e E(D). If W = (v0, e1, v1, e2,..., e„, vn) is a walk in D, then the quotient walk WT of W is defined to be the walk W = ((v0)T,e1, (v1)T,e2,...,en, (vn)T). Note that for every j, 0 < j < |W| = |WT|, we have Z(0Wj) = Z(0(WTj). We emphasize that we consider these quotient digraphs as simple digraphs in the sense that if there are several edges in the same direction between two sets in t, then the quotient digraph contains exactly one directed edge between the respective vertices. But of course these quotient graphs might contain loops if there is an edge (u, v) e E(D) for some u e vT.
Let G be a group acting transitively on D and let H be a normal subgroup of G. Then the orbits of H on V(D) give rise to an imprimitivity system t of G on V(D). The respective quotient digraph DT is usually denoted by DH.
As mentioned above, if D is transitive, then R+ and R- give rise to imprimitivity systems of Aut(D) on D. The respective quotient digraphs are denoted by D/R+ and D/R- and can be described easily (see e. g. [8]). The digraph D/R+ either is (1) a finite directed cycle or (2) a two-way infinite directed line or (3) an infinite regular directed tree with indegree 1 and outdegree > 1. Considering R- the first two possibilities are the same, but if D/R- is neither of these digraphs, then it is a regular tree with outdegree 1 and indegree > 1 .
2 Motivation and main result
The aim of this paper is to investigate the interplay between properties of groups and properties of reachability relations in their Cayley digraphs.
For example, as a consequence of the last paragraph of the previous section, we immediately see that the quotient digraphs with respect to R+ of Cayley digraphs of finitely generated groups with polynomial or intermediate growth are either finite directed cycles or directed lines. Further, from [6, Theorem 4.12] we know that a finitely generated group
A. Mainte: et al.: Reachability relations, transitive digraphs and groups
87
G has exponential growth if for at least one Cayley digraph D of G, at least one of the exponents exp+(D) or exp-(D) is infinite.
Additionally, by Gromov's important result [3], a finitely generated group has polynomial growth if and only if it contains a normal nilpotent subgroup of finite index. Hence the following question arises naturally: What can be said about properties of our reachability relations in Cayley digraphs of finitely generated groups with polynomial growth?
In fact we carry out our considerations by assuming that nilpotent groups act with finitely many orbits on digraphs. The results for Cayley digraphs of groups with polynomial growth are then obtained as corollaries. The main result of this paper is the following theorem.
To avoid ambiguity, we recall the definition of nilpotent groups: For a group G = G0,
let Gi+1 = [G0, G®] for i > 0. If G = G0 > G1 > ... > Gr > Gr+1 = 1 then we say that G is nilpotent of class r.
Theorem 2.1. Let a group G act transitively on a connected digraph D, and let N < G be a normal nilpotent subgroup of class r acting with m orbits on D, where 1 < m < to. Then exp+(D) = exp-(D) < m(r + 2) — 1.
Although we are mainly interested in properties of our relations in Cayley digraphs of finitely generated groups, we emphasize that - with the exception of those results explicitely formulated for finitely generated groups - we never assume that the graphs in consideration are locally finite.
3 Auxiliary results
In this section we prove several results which will be useful for our main investigations, carried out in Section 4.
Lemma 3.1. Let D be a digraph with minimal in- and outdegree at least 1 and let k > 1 be an integer. Then for any two vertices u,v G V(D) we have that uR+v if and only if there exists a walk W G R+[u,v] that is a concatenation of walks of the form (u0,1, u1,1,..., 1, uk, —1, uk+1, —1,..., —1, u2k). An analogous result holds for the relation R-.
Proof. We prove the assertion for the relation R+ and leave the analogous proof for R- to the reader.
To this end suppose uR+v and let W' = (u0, e1, u1, e2, u2, £3,..., £n, un) G R+[u, v]. Observe that, since the minimal in- and outdegrees of D are at least 1, there is a directed walk of any prescribed positive or negative weight starting at any vertex of D.
A walk W g R+ [u, v], as described in the statement of the lemma, can now be obtained from W' inductively by inserting a concatenation of such a directed walk of appropriate length with its inverse at each vertex u® for which £ = £i+1 and Z(0W/) is not 0 or k.
□
For a group G, a positive integer k, and subsets S, T C G let ST = {st|s G S, t G T}, Sk = Sj^ and S-k = S-1 •• ■ S-1,.
k k
Corollary 3.2. Let D = Cay(G, S) be a Cayley digraph of a group G with respect to the generating set S. Then for any integer k > 1 and any g G G we have that R+(g) = gR+ (1) = g(SkS-k> and R-(g) = gR-(1) = g(S-kSk>.
88
Ars Math. Contemp. 8 (2015) 149-162
Proof. We prove the assertions for R+ and leave the analogous proof for Rfc to the reader. The fact that R+(g) = gR+ (1) is obvious since G has a natural left regular action on D while R+(1) = (SkS-k) follows fromLemma 3.1.	□
Lemma 3.3. Let D be a digraph and let t be a partition of the vertex set of D. Suppose that for each u,v G V (D) with (uT, vT) G E(DT) there exist u' G uT and v' G vT such that (u, v') and (u', v) are arcs of D. Then for each k > 1 and each u,v G V (D) we have that uT R+vT if and only if there exists some w G vT such that uR+w. An analogous result holds for the relation R-.
Proof. We prove the result for R+ and leave the analogous proof for R- to the reader. Let
k > 1 and let u,v G V (D).
Suppose first that for some w G vT we have that uR+w and let W G R+ [u, w]. Since vT = wT, the walk WT is contained in R+[uT, vT]. This proves one implication.
Suppose now that uTR+vT and let W = (uT,e1,x1,e2,... ,xn,en+1,vT) G R+[uT, vT]. Then by assumption one can successively find representatives Xj G Xj and w G vT such that W = (u, e1,x1 ,e2,x2,e3,..., xn, £n+i, w) G R+[u, w].	□
Remark 3.4. Observe that the condition of the above lemma is satisfied if t consists of the orbits of some group acting on D.
Lemma 3.5. Let a group G act transitively on a digraph D and let H be a normal subgroup of G such that each of its subgroups is normal in G. Then exp+(D) < exp+(DH) +1 and exp-(D) < exp-(DH) + 1.
Proof. We prove the result for exp+(D). The proof for exp-(D) is analogous and is left to the reader. If exp+(DH) = to, there is nothing to prove. We may thus assume that exp+(DH) = k for some integer k > 0.
To show that exp+(D) < k +1 let u G V(D) and v G R+(u) be arbitrary. Consider the equivalence class B = R++1(u) and the H-orbit Hu. Note that both of these sets are blocks of imprimitivity for the action of G on V(D). Let K be the setwise stabilizer in H of the set B. Note that the K-orbit of u is K u = H u n B and is thus a block of imprimitivity for G. Moreover, by assumption on H the subgroup K is normal in G, and so the block system generated by the block K u coincides with the block system given by the orbits of K. Consequently, any two vertices within the same H-orbit are R++1 related if and only if they belong to the same K-orbit.
We first show that exp+(DK) < k. If this is not the case, then there exists Kw G V(Dk) such thatKw G R++1(Ku) \ R+(Ku). By Lemma 3.3 there exists w' G Kw such that uR++1w'. Moreover, since exp+(DH) = k there exists z G Hw' = Hw such that uR+z. But then zR++1w', and so Kz = Kw' = Kw, implying that Kw G R+(Ku), a contradiction.
Hence exp+(DK) < k. But then Kv G R+(Ku) = R++1(Ku) in Dk, and by Lemma 3.3 there exists some x G Kv such that uR++1x. Since x G Kv we have that xR++1v, and so uR++1v holds.
Since u and v were arbitrary subject to the condition that uR+v, this shows that
exp+(D) < k +1.	□
Lemma 3.6. Let a group G act transitively on a digraph D with finite exponents exp+(D) and exp-(D). Furthermore, let t denote the imprimitivity system of G on V(D) which is
A. Mainte: et al.: Reachability relations, transitive digraphs and groups
89
induced by the equivalence classes with respect to R+ or R . Then every g e G which leaves invariant at least one block of t leaves invariant all blocks of t.
Proof. Since the exponents exp+(D) and exp-(D) are both finite, [6, Corollary 3.5] implies that R+ = R-, and so the discussion from the last paragraph of the first section implies that DT is a finite cycle or the two-way infinite directed line. Hence, the only automorphism of DT which fixes a vertex is the identity. On the other hand, every automorphism g e G which leaves invariant a block of t induces an automorphism of DT fixing a vertex of DT, and the result follows.	□
4 R+ and R- in transitive digraphs
We start with a simple observation concerning Cayley digraphs of abelian groups.
Proposition 4.1. Let G be an abelian group acting transitively on a digraph D. Then
exp+(D) = exp-(D) = 1.
Proof. Since G is abelian, D is a Cayley graph of G. Then Corollary 3.2 implies that R+ = R- and [6, Corollary 3.4] implies that R+ = R+ = R- = R-, as claimed. □
We now generalise this result to nilpotent groups.
Theorem 4.2. Let G be a nilpotent group of class r acting transitively on a digraph D. Then exp+(D) = exp-(D) < r +1.
Proof. We first show that exp+ (D) < r + 1. The proof is carried out by induction on r. If r = 0, then G is an abelian group and Proposition 4.1 applies.
Suppose now that r > 1. As G(r+1) = 1, we have that H = G(r) is contained in the center of G, and so each of its subgroups is normal in G. Hence Lemma 3.5 implies that exp+(D) < exp(DH) + 1. Now, the quotient group G/H is a nilpotent group of class r - 1 and acts transitively on the quotient digraph DH. By induction hypothesis we thus have that exp+(DH) < r. Consequently, exp+(D) < r + 1, as claimed.
The fact that exp-(D) < r +1 follows by analogous arguments. Then [6, Corollary 3.5], implies that exp+ (D) = exp-(D).	□
The next example shows that the bound from the above theorem is tight, that is, for every positive integer r there exists a nilpotent group G of class r and a digraph D on which G acts transitively such that exp+(D) = r + 1 = exp- (D) holds.
Example 4.3. Already for the smallest nonabelian finitely generated nilpotent group, the dihedral group D8 of order 8 (of nilpotency class 1), this is the case. Let us write D8 =
(/, ai,a2 |f2 = a2 = a2 = 1,/ai/-1 = aia2,/a2 = «2/, aia2 = a2ai). Then for the Cayley digraph D = Cay(D8, {/, /ai}) we clearly have that exp+(D) = exp-(D) = 2.
In fact, this example happens to be the smallest member of the following infinite family. Let n > 1 be an integer and let Gn be the semidirect product of the elementary abelian group Zn by the cyclic group Z2n-i generated by Gn = (/, ai, a2,..., an), where / is of order 2n-\ the are involutions commuting with each other and /a/-i = ajai+i holds for all i, 1 < i < n, while / and an commute. One can verify that for S = {/, /aia2 • • • an} we have that (S®S-i) = (ai, a2,..., a4) holds for all i, 1 < i < n, and so Corollary 3.2 implies that exp+(Cay(Gn, S)) = n. Moreover, it can be verified that Gn is nilpotent of class n - 1. Indeed, we have that G(i) = (ai+i, ai+2,..., an) holds for
90
Ars Math. Contemp. 8 (2015) 149-162
each i, 1 < i < n - 1, and of course then G(n) = 1. The Cayley graph Cay(Gn, S) thus attains the bound from the above theorem.
We shall now see, that the above theorem cannot be generalized to solvable groups.
Example 4.4. The lamplighter group L is the wreath product Z2 I Z. The standard representation for L is
(a, t|a2, [tmat-m, tnat-n], m, n G Z).
If we consider the Cayley digraph of L with respect to the generating set S = {t, at}, then this Cayley digraph is the horocyclic product of two directed trees with indegree 1 and outdegree 2. In this digraph R+ = R+ clearly holds for all k G Z+. This shows that for solvable groups we cannot expect a result like Theorem 4.2.
As was shown in [6], a connected, locally finite, transitive digraph D has exponential growth if at least one of the exponents exp+ (D) or exp-(D) is infinite. Hence these exponents must be finite if a connected, locally finite, transitive digraph D does not have exponential growth. So the question arises if we can find a bound on exp+ (D) and exp- (D) which depends on the growth rate of D or on certain properties of groups acting transitively on D. In the sequel we show that this is indeed possible.
We first consider the case where a digraph D allows a transitive action of a group G containing a normal abelian subgroup, acting with finitely many orbits on D, thereby obtaining a tight bound for exp+ (D) and exp- (D). We then explore a more general situation where a transitive group G contains a normal nilpotent subgroup acting with finitely many orbits on D. We start by proving two auxiliary results.
Lemma 4.5. Let D be a connected digraph, and let G be a transitive subgroup of Aut(D) having a normal subgroup H < G with m, 1 < m < to, orbits on D. If for some (and hence every) u G V (D) the set R+(u) is contained in Hu, then the following hold:
(i)	For every v G V(D) the set R+(v) is contained in Hv.
(ii)	The quotient digraph DH is a directed cycle.
Proof. Observe that if m =1 there is nothing to prove, so we may assume m > 2.
To prove (i) we show that R+ (v) C Hv for all v G V(D) and all k. We do that by induction on k. The base of induction (k = 1) holds by assumption. Let now k > 1 and suppose that R+ (v) C Hv holds for all j < k. Pick an arbitrary vertex v G V(D) and let w G R++i(v). Let v = v0, w = vn and choose a walk W = (v0,1, vi,..., vn_i, -1, vn) G R++1 [v, w]. Suppose first that for all i, 0 < i < n, we have that Z(0Wj) > 0. In this case v1R+vn_1, and so induction hypothesis implies that vn-1 G Hv1, that is, vn-1 = hv1 for some h G H. Then (hv0, vn-1) G E(D), and so hv0R+vn. Then, by assumption, we have that hv0 g hvn, and so v G Hw (recall that v = v0 and w = vn). Suppose now that 0 < i1 < i2 < • • • < it = n are such that Z(0Wj.) = 0. By the above argument vix G Hv, vi2 G Hv^,... , w G Hvit-1. Hence v G Hw, which proves (i).
We now prove (ii). Let Hv be an H-orbit. Since D is connected and H has at least two orbits which are blocks of imprimitivity for G, there exists an H-orbitH w = H v such that (Hw,H v) G E(Dh). It follows that there exists a vertex w' G Hw with (w', v) G E(D). Consequently, the quotient digraph DH must have indegree one (for otherwise we obtain a vertex x G Hw which is R+-related to w'). Since DH is finite, it is a simple directed cycle.	□
A. Mainte: et al.: Reachability relations, transitive digraphs and groups
91
Lemma 4.6. Let D be a digraph, and let G be a transitive subgroup of Aut(D) having an abelian normal subgroup H < G with m, 1 < m < to, orbits on D. If for some (and hence any) u G V(D) the set R+(u) is contained in Hu, then exp+(D) = exp_(D) < m.
Proof. We prove that exp+ (D) < m and leave the analogous proof that exp_ (D) < m to the reader.
If m = 1, then D is a Cayley digraph of an abelian group, so Proposition 4.1 applies. We can thus assume that m > 2. Let A = Hu for some u G V(D).
We first construct an auxiliary digraph D* with vertex set A and an edge (w, v) whenever there exists a directed path of length m in D from w to v. The restriction of H on A acts regularly on A. The digraph D* thus is a Cayley digraph of an abelian group (possibly disconnected). Therefore exp+(D*) < 1 by Proposition 4.1.
Now, let vR+w for some v, w G V (D) and let us show that in this case vR+w holds. By definition of R+ we have that vR+w holds for some integer k. Then Lemma 3.1 implies that there exists a walk in R+[v, w] which is a concatenation of walks of the form W = (v0,1, vi, 1,..., 1, vk, -1, vk_i, -1,..., -1, v2k). By transitivity it suffices to prove that v0R+v2k. Let t, r with 0 < r < m be the integers such that k = tm + r. By Lemma 4.5 the vertices vo, vm, v2+,..., vim and v2fc, v2fc_m, v2k_2+,..., v2k_tm all belong to the H-orbit Hv0. Hence v2k = hv0, vtm = hl v0 and v2k_tm = h2v0 for some h, hi, h2 G H. Now, 0Wtm • (hlh-1 ((2fc_tm)W2fc)) is a walk from v0 to x = hlh--1 v2fc = hlh--lhv0. As H is abelian, x = hh- hl v0. Therefore, hh- (tmW2k_tm) G R+[x, v2k], and so r < m implies that v0R+ v2k if and only if v0R+x, that is, we can assume r = 0. Since v0 G Hv, we have v0 = ho v for some h0 G H. It follows that the walk W corresponds to a walk W* G R+[h0, hih_ihh0] in D*. Since exp+(D*) < 1, the walk W* can be replaced by a walk in R+[h0, hih_ihh0], implying that W can be replaced by a walk in R+[v0, v2k].
Therefore, R+ C R+, implying that R+ = R+. Analogously, it can be shown that R_ = Rm. Then [6, Corollary 3.5] completes the proof.	□
To prove the next theorem we need the following result from [6].
Proposition 4.7. ([6], Proposition 3.11) Let D be a digraph, let t be the set of equivalence classes of R+, and let u G V(D). Then, for any v G V(D) and any k > 2 we have that uR+v if and only if uT R+_ivr. An analogous assertion holds for R_ when taking the quotient with respect to Ri-.
Theorem 4.8. Let D be a digraph and let G < Aut(D) be a transitive subgroup having an abelian normal subgroup H acting with m, 1 < m < to, orbits on V(D). Then exp+(D) = exp_(D) < m.
Proof. We prove that exp+(D) < m and leave the analogous proof for exp_(D) to the reader. We proceed by induction on m. If m = 1, then the result follows from Proposition 4.1. Suppose the assertion holds for all n < m, m > 2, and suppose that H has m orbits on D. If for some u G V(D) the set R+(u) is contained in Hu, then Lemma 4.6 applies.
Assume now that the equivalence classes with respect to R+ are not contained in the orbits of H and consider the quotient digraph D/R+. Let K be the kernel of the action of G on D/R+ and let N = HK/K = H/(H n K) be the induced faithful action of H on D/R+. Observe that, since the Ri-equivalence classes are not fully contained in the H-orbits, N acts with at most + orbits on D/R+. By induction hypothesis (note that N is an
92
Ars Math. Contemp. 8 (2015) 149-162
abelian normal subgroup of G/K) we have that exp+(D/R+) < y. By Proposition 4.7 it follows thatexp+(D) = exp+(D/R+) + 1 < < m.
Analogously it can be shown that exp_(D) < m. Then again [6, Corollary 3.5] completes the proof.	□
Proof of Theorem 2.1
Let a group G act transitively on a connected digraph D, and let N < G be a normal nilpotent subgroup of class r acting with m orbits on D, where 1 < m < to.
We first prove that exp+(D) < m(r + 2) — 1. The proof is done by induction on m.
If m =1, then the result holds by Theorem 4.2. If m > 2 we distinguish two cases, depending on the structure of DN.
Case 1. Dn is not isomorphic to a directed cycle on m > 2 vertices.
In this case Lemma 4.5 implies that, for any v e V(D), the set R+ (v) is not completely contained in one orbit of N. Let t denote the imprimitivity system of G on D consisting of the equivalence classes with respect to R+. Then the permutation group GT, induced by the action of G on t, acts transitively on DT. Furthermore, NT acts with at most y orbits. In addition NT is nilpotent of class at most r. Then, by induction hypothesis, exp+ (Dt) < y (r + 2) — 1 holds and the result follows by Proposition 4.7.
Case 2. DN is isomorphic to a directed cycle C = (ci,..., cm) on m > 2 vertices.
Let O1,..., Om denote the orbits of N on V(D) which correspond to the vertices c1,..., cm e Dn . Then of course there is no edge in D which connects two vertices which are both contained in the same orbit. Furthermore, all edges of D are directed from Oj to Oi+1, 1 < i < m, where indices are taken modulo m. Then for every v e O,, 1 < i < m, R+(v) C O, holds. Of course exp+(D) < m — 1 holds if R^ (v) = O, for some v e O, and some i, 1 < i < m.
Hence we only have to consider the case when R+_1(v) is properly contained in O, for every i, 1 < i < m, and every vertex v e O,. By Bt, i e I, we denote the equivalence classes of Ry_1 on O1. For v e O1, let P(v) denote the set of all directed paths starting at v and containing exactly one vertex from each orbit O,, 1 < i < m. Since DN is isomorphic to a directed cycle with m vertices and N acts transitively on each of its orbits, P(v) = 0 for all v e O1. Furthermore, for i e I let S be the subdigraph of D induced by the vertices of the union UveB P(v). Note that since the sets are different equivalence classes with respect to Ry_1, the digraphs St, i e I, are pairwise disjoint.
We first define Vm as the set of all directed paths P — (v1,..., vm+1) in D where vj e Oj for 1 < j < m and vm+1 e O1. Analogously we define P_m as the set of all inverses of the paths in Pm. Furthermore, let Ry_1 denote the set of all walks which are contained in Ry_1 [u, v] for some vertices u, v e O1.
Let v1, v2 e O1 now satisfy v1R+v2. If v1 and v2 are both contained in one and the same set Bt, i e I, then of course v1R+_1v2 holds.
Now let v1 e Btl and v2 e Bl2, i1 = i2. Then there is a walk W e R+ [v1, v2] which is the concatenation of finitely many paths and walks which are contained in Pm, P _m or Ry_1. Let D' now be the digraph with vertex set I with (i1, i2) e E(D') whenever there exists a path P e Pm with origin in Bt1 and terminal vertex in Bl2. Observe that, in general, the digraph D' might not be locally finite. Nevertheless, the restriction of N to O1 induces a transitive group acting on D' which is nilpotent of class at most r. Thus Theorem 4.2 implies that exp+ (D') < r + 1.
A. Mainte: et al.: Reachability relations, transitive digraphs and groups
93
Observe that, by Lemma 3.1, we can assume that the walk W is the concatenation of t paths from Pm, followed by a walk in R^-i and then t paths from P-m, for some nonnegative integer t. Let u0, u1,..., u2i+1 be the vertices of W, contained in O1, given in the order they are met when traversing W. Thus u0, u1,..., ut-1 are the origins of the paths from Pm while the vertices ut+1, ut+2,..., u2t are the origins of the paths from P-m. The walk W thus naturally gives rise to the walk W' = (i0, i1,..., tt-1, tt+1, ti+2,..., t2t+1) in D', where for each i we have that u G (observe that ut G Blt+1 = Blt). Of course W' g r+[i0, t2t+1], and so exp+(D') < r +1 implies that there is a walk W' g R++1[t0, i.2i+1]. Since the sets Bli are equivalence classes of the relation R^^ on D it is now clear that this walk gives rise to some walk in R^^)^ [v1, v2].
Since exp- (D) < m(r + 2) - 1 holds by similar arguments, [6, Corollary 3.5] implies that exp+(D) = exp-(D).	□
Corollary 4.9. Let G be a finitely generated group, let N be a normal nilpotent subgroup of finite index m in G and let D denote a Cayley digraph of G with respect to some finite generating set S. Then exp+ (D) = exp-(D) < m(r + 2) — 1 holds, where r is the nilpotency class of N.
It is natural to ask if this bound is tight. All examples we know in fact satisfy the inequality exp+(D) < m(r + 1). We thus pose the following problem.
Problem 4.10. Is it true that exp+(D) = exp-(D) < m(r + 1) holds for the Cayley digraphs of groups described in Corollary 4.9?
For Cayley digraphs D of finitely generated torsion-free groups G with polynomial growth we even obtain bounds for exp+ (D) and exp-(D) which only depend on the growth degree. To formulate the result we first have to consider GL(n, Z).
Theorem 4.11. (see e.g. [7]) The orders of the finite subgroups of GL(n, Z) are bounded by some function g(n) ofn alone.
Theorem 4.12. (see e.g. [7]) Let G be a finitely generated torsion-free group with polynomial growth of degree d. Then G contains a normal nilpotent subgroup of class less than V2d and index at most g(d), where g(d) is the function of Theorem 4.11.
Corollary 4.13. Let G be a finitely generated torsion-free group with polynomial growth of degree d. Then for any Cayley digraph D of G, exp+ (D) and exp- (D) are bounded by g(d)(V2d + 2) — 1, where g(d) is the function of Theorem 4.11
We conclude the paper with the following observations. Let G < Aut(D) act transitively on a digraph D with finite exponents exp+ (D) and exp- (D). Then Lemma 3.6 implies that the equivalence classes of the relation R+ = R- are orbits of a normal subgroup of G. Thus, if this relation is not universal and if the digraph has indegree or outdegree at least 2, then this normal subgroup of G is proper and not trivial. As a consequence, if G is simple, the relation R+ = R- is universal on D. As was already mentioned above it was shown in [6, Theorem 4.12] that a connected infinite locally finite transitive digraph D has exponential growth if at least one of the exponents exp+(D) or exp-(D) is infinite. At this point we recall the following problem from combinatorial group theory (see e.g. [1]), which was originally posed by R. I. Grigorchuk.
94
Ars Math. Contemp. 8 (2015) 149-162
Problem 4.14. Does every finitely generated infinite simple group have exponential growth?
The following proposition then allows to formulate a conjecture which closely relates this problem to reachability relations.
Proposition 4.15. If a finitely generated infinite simple group G does not have exponential growth, then for every finite generating set S of G there is a finite integer kS > 1, such that R+ = R— is universal in C(G, S).
Proof. Follows immediately from [6, Theorem 4.12] and Lemma 3.6.	□
Conjecture 4.16. Let G be a finitely generated infinite group. Then there is a finite generating set S of G such that for the Cayley digraph D of G with respect to S one of the following holds:
•	At least one of the exponents exp+(D) or exp-(D) is infinite and hence D has exponential growth.
•	Both, exp+(D) and exp-(D) are finite and the reachability relations R+ and R-are not universal on D.
Observe that by Proposition 4.15 the validity of this conjecture would provide a positive answer to Grigorchuk's problem.
References
[1]	G. Baumslag, A. G. Myasnikov and V. Shpilrain, Open problems in combinatorial group theory. Second edition, Combinatorial and geometric group theory, S. Cleary, R. Gilman, A. G. Myasnikov, V. Shpilrain, eds., Contemporary Mathematics 296, AMS 2002.
[2]	P. J. Cameron, C. E. Praeger and N. C. Wormald, Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 13 (1993), 377-396.
[3]	M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Etudes Sci. Publ. Math. 53 (1981), 53-78.
[4]	M. DeVos, B. Mohar and R. Samal, Reachability in highly arc-transitive digraphs, arXiv:1110. 2945.
[5]	A. Malnic, D. Marusic, R. Moller, N. Seifter, V. Trofimov and B. Zgrablic, Highly arc transitive digraphs: reachability, topological groups, Europ. J. Combinatorics 26 (2005), 19-28.
[6]	A. Malnic, D. Marusic, N. Seifter, P. Sparl and B. Zgrablic, Reachability relations in digraphs, Europ. J. Combin. 29 (2008), 1566-1581.
[7]	A. Mann, How groups grow, LMS Lecture Notes Ser. 395, Cambridge Uni. Press, 2012.
[8]	N. Seifter and V. I. Trofimov, Reachability relations and the structure of transitive digraphs, Electron. J. Combin. 16 (2009), R26.