ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA B (2015) 29-34
Arc-transitive graphs of valency 8 have a semiregular automorphism*
Gabriel Verretf
Centre for Mathematics of Symmetry and Computation, The University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia. Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška 8, 6000 Koper, Slovenia.
Received 23 May 2013, accepted 16 October 2013, published online 14 April 2014
One version of the polycirculant conjecture states that every vertex-transitive graph has a non-identity semiregular automorphism that is, a non-identity automorphism whose cycles all have the same length. We give a proof of the conjecture in the arc-transitive case for graphs of valency 8, which was the smallest open valency.
Keywords: Arc-transitive graphs, polycirculant conjecture, semiregular automorphism. Math. Subj. Class.: 20B25, 05E18
1 Introduction
All graphs considered in this paper are finite and simple. An automorphism of a graph r is a permutation of the vertex-set V(T) which preserves the adjacency relation. The set of automorphisms of r forms a group, denoted Aut(T). A graph r is said to be G-vertex-transitive if G is a subgroup of Aut(T) acting transitively on V(T). Similarly, r is said to be G-arc-transitive if G acts transitively on the arcs of r. (An arc is an ordered pair of adjacent vertices). When G = Aut(T), the prefix G in the above notation is sometimes omitted.
A group G acting on a set Q is semiregular on Q if the stabiliser Gu is trivial for every w G Q; note that this implies that the action is faithful. An element g G G is called semiregular provided that it generates a semiregular group. Equivalently, an element g G G is semiregular if (g) acts faithfully on Q and that all of the cycles of the permutation induced by g have the same length.
* Dedicated to Dragan Marusic on the occasion of his 60th birthday.
^The author is supported by UWA as part of the Australian Research Council grant DE130101001. E-mail address: gabriel.verret@uwa.edu.au (Gabriel Verret)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
30
Ars Math. Contemp. 8 (2015) 133-148
In 1981, Marusic conjectured [7] that every vertex-transitive graph with at least two vertices has a non-identity semiregular automorphism. This is sometimes called the poly-circulant conjecture. While there has been a lot of work on this conjecture and some of its variants, it is still wide open. There has been progress in some directions (see [6] for a survey). For example, the conjecture has been settled for graphs of certain orders [2, 7, 8] and for graphs of valency at most four [1, 8].
In the arc-transitive case, slightly more can be said, but we first need a few definitions. If r is a graph and G < Aut(T) then denotes the permutation group induced by the action of the vertex-stabiliser Gv on the neighbourhood r(v) of the vertex v. A permutation group is called quasiprimitive if each of its nontrivial normal subgroup is transitive, while a vertex-transitive graph r is called locally-quasiprimitive if Aut(r)i(v) is quasiprimitive. Using this terminology, we have the following theorem due to Giudici and Xu.
Theorem 1.1. [5, Theorem 1.1] A locally-quasiprimitive vertex-transitive graph has a non-identity semiregular automorphism.
A transitive group of prime degree is clearly quasiprimitive (in fact primitive) and hence it follows from Theorem 1.1 that arc-transitive graphs of prime valency have a non-identity semiregular automorphism. In an upcoming paper [4], the author and Giudici deal with the case of arc-transitive graphs of valency twice a prime. The main result of this paper is to prove the polycirculant conjecture for arc-transitive graphs of valency 8, the smallest open valency.
Theorem 1.2. An arc-transitive graph of valency 8 has a non-identity semiregular automorphism.
The prime 2 plays a special role in our proof. In some sense, we use the fact that any proper factorisation of 8 must include 2 as one of the factors. In particular, if r is a G-arc-transitive graph of valency 8 and N is a normal subgroup of G that is not semiregular and that has at least three orbits then the quotient graph r/N is an arc-transitive graph of valency either 2 or 4. In the former case, we can view r/N as an asymmetric arc-transitive digraph of out-valency 4, which turns out to be very useful (see Theorem 2.7). In the latter case, the valency of r is exactly twice the valency of r/N which gives us very precious information about the kernel of the action of G on N-orbits (see the proof of Theorem 1.2).
This special role of the prime 2 is also evident in the proof of the case of valency twice a prime [4]. In the more general case of valency a product of two primes, Xu [13] has made significant progress and it seems the bottleneck is the case when G is solvable. (See [3] for some results in this case.)
2 Preliminaries 2.1 Permutation groups
We start with a few very basic lemmas about permutation groups. Since the proofs are short, we include them for the sake of completeness.
Lemma 2.1. Let p be a prime and let G be a transitive permutation group of degree a power of p. Then G contains a non-identity semiregular element.
Proof. Let S be a Sylow p-subgroup of G. By [12, Theorem 3.4'], S is transitive. Let z be a non-identity element of the centre of S. If z fixes a point then it must fix all of them, which is a contradiction. It follows that z is semiregular.	□
G. Verret: Arc-transitive graphs of valency 8 have a semiregular automorphism
31
Lemma 2.2. If G is a transitive permutation group with a non-trivial abelian normal subgroup N that has at most two orbits, then N contains a non-identity semiregular element.
Proof. If N is semiregular then we are done. We may thus assume that there exists a non-identity element n G N fixing some point v. Since N is abelian, n fixes the N-orbit vN pointwise. It follows that N has exactly two orbits. Let u be a point not in vN and let g G G such that vg = u. Then n acts semiregularly on uN, while ng fixes uN pointwise and acts semiregularly on vN. It follows that nng is a non-identity semiregular element of N.	□
Lemma 2.3. Let G be a permutation group and let K be a normal subgroup of G such that G/K acts faithfully on the K-orbits. If G/K contains a semiregular element gK of order r coprime to |K | then G contains a semiregular element of order r.
Proof. There exists k G K such that gr = k. Let h = g|k|. Since |k| and r are coprime, it follows that |h| = r and hK is a non-identity power of gK hence it is semiregular. We now show that h is semiregular. Suppose h® fixes a point v for some integer i. Then hlK = (hK)® fixes vK and, since hK is semiregular, h®K = K. This implies that h® G K. Since h has order coprime to |K|, it follows that h® = 1.	□
Lemma 2.4. A transitive permutation group of degree 8 is either primitive or it is a {2, 3}-group.
Proof. Let G be a transitive permutation group of degree 8 that is not primitive. Then G has a non-trivial system of imprimitivity, with blocks of size either 2 or 4. It follows that G is isomorphic to a subgroup of Sym(4) I Sym(2) or Sym(2) I Sym(4) and hence it is a {2,3}-group.	□
We also need the following folklore lemma
Lemma 2.5. Let p be a prime, let r be a connected graph and let G < Aut(r). If, for every v G V(r), |Gi(v) | is coprime to p, then so is |Gu | for every u G V(r).
Proof. We prove this by contradiction. Let p be a prime dividing |Gu | for some u G V(r) and let g G Gu have order p. Since g is non-trivial, it must move some vertex. Let w be a vertex of r moved by g at minimal distance from u. By the connectivity of r, there is a path u, ui,..., ut, w such that g fixes each u®. Then g G Gut and g acts nontrivially on r(ut). Thus p divides |Gr(ut) | and the result follows.	□
2.2 Quotient graphs
We will need some basic facts about quotient graphs, which we now collect. (For a reference, see [11] for example.)
Let r be a graph and let N < Aut(r). The quotient graph r/N is the graph whose vertices are the N-orbits with two such N-orbits vN and uN adjacent whenever there is a pair of vertices v' G vN and u' G uN that are adjacent in r. Clearly, if r is connected then so is r/N.
Let r be a G-arc-transitive graph, let N < G and let K be the kernel of the action of G on N-orbits. Then K = NKv < G, G/K < Aut(r/N) and r/N is G/K-arc-transitive. If N has at least 3 orbits then the valency of r/N is at least 2 and divides the valency of r. If r/N has the same valency as r then N = K and K is semiregular.
32
Ars Math. Contemp. 8 (2015) 133-148
Some of these facts are used in the proof of the following lemma.
Lemma 2.6. Let p be an odd prime and let r be a connected 4-valent G-arc-transitive graph such that p divides |V(F) |. If G is solvable then G contains a semiregular element of order p.
Proof. The proof goes by induction on |V(r)|. Let v e V(r). If is a 2-group then it follows from Lemma 2.5 that Gv is a 2-group and every element of G of order p is semiregular. We thus assume that G^(v) is not a 2-group and, since it is a transitive group of degree 4, it is 2-transitive. Since G is solvable, it contains a non-trivial normal elementary abelian q-group N. If N has at most two orbits then p = q and the result follows from Lemma 2.2.
From now on, we assume that N has at least three orbits. Since G^(v) is 2-transitive, this implies that r/N is 4-valent and hence N is semiregular and G/N acts faithfully on r/N .If p = q then N contains a semiregular element of order p and the conclusion holds. Suppose now that p = q. Then r/N is a connected, 4-valent G/N-arc-transitive graph. Sincep is coprime to |N|, it divides |V(r/N)|. By the induction hypothesis, G/N contains a semiregular element of order p. The result then follows from Lemma 2.3.	□
2.3 Digraphs
Finally, we will need a few notions about digraphs. We follow the terminology of [10] closely. A digraph r consists of a finite non-empty set of vertices V(r) and a set of arcs A(r) C V x V, which is an arbitrary binary relation on V. A digraph r is called asymmetric provided that the relation A(r) is asymmetric.
If (u, v) is an arc of r then we say that v is an out-neighbour of u and that u is an in-neighbour of v. The symbols r+(v) and r-(v) will denote the set of out-neighbors of v and the set of in-neighbors of v, respectively. We also say that u is the tail and v the head of (u, v), respectively. The digraph r is said to be of out-valence k if |r+ (v) | = k for every v e V(r).
An automorphism of r is a permutation of V(r) which preserves the relation A(r). The set of automorphisms of r forms a group, denoted Aut(r). We say that r is arc-transitive provided that Aut(r) acts transitively on A(r).
We say that two arcs a and b of r are related if they have a common tail or a common head. Let R denote the transitive closure of this relation. The alternet of r (with respect to a) is the subdigraph of r induced by the R-equivalence class R(a) of the arc a. (i.e. the digraph with vertex-set consisting of all heads and tails of arcs in R(a) and whose arc-set is R(a)). If the alternet with respect to (u, v) contains an arc of the form (v, w) then this alternet is called degenerate.
If the alternet of the arc (u, v) is non-degenerate then it is a connected bipartite digraph where the first bipartition set consists only of sources while the second bipartition set contains only sinks. An important case occurs when this alternet is in fact a complete bipartite digraph in which case we will simply say that the alternet is complete bipartite. We say that r is loosely attached if r has no degenerate alternets and the intersection of the set of sinks of one alternet intersects the set of sources of another alternet in at most one vertex.
We define the digraph of alternets Al(r) of r as the digraph the vertices of which are the alternets of r and with two alternets A and B forming an arc (A, B) of Al(r) whenever the intersection of the set of sinks of A with the set of sources of B is non-empty.
G. Verret: Arc-transitive graphs of valency 8 have a semiregular automorphism
33
We are now ready to prove the following theorem.
Theorem 2.7. Let r be a connected asymmetric arc-transitive digraph of out-valence 4. Then r has a non-identity semiregular automorphism.
Proof. The proof goes by induction on |V(r)|. Since r is connected and arc-transitive (and finite), it follows that it is vertex-transitive and strongly connected (see for example [9, Lemma 2]).
Let v e V(r) and let G = Aut(r). Without loss of generality, we may assume that every prime that divides |G| also divides |Gv |. If Gv is a 2-group then the conclusion follows from Lemma 2.1. We may thus assume that Gv is not a 2-group and hence neither
r+(v)	r+(v)
is Gv . Since Gv is a transitive permutation group of degree 4, it is 2-transitive.
Since f has out-valence 4, Gr (v) is a {2,3}-group, hence so are Gv and G and therefore G is solvable by Burnside's Theorem. It follows that G has an abelian minimal normal subgroup N. If N is semiregular then the conclusion holds. We may thus assume that N is not semiregular and hence N^ (v) is a non-trivial normal subgroup of Gr (v) and therefore is transitive. The same argument yields that Nr (v) is also transitive.
Let (u, v) be an arc of r. We have just seen that n£+(u) and Nr (v) are both transitive. This implies that r+(u) C vN and r-(v) C uN. On the other hand, N is abelian and hence N„ fixes uN pointwise and Nv fixes vN pointwise. It follows that the alternet of r with respect to (u, v) is not degenerate and is complete bipartite.
If r is not loosely attached then it follows that, for every vertex x, there exists at least one other vertex y such that r- (x) = r- (y) and r+ (x) = r+ (y). It follows easily that r has a non-identity semiregular automorphism in this case.
We may thus assume that r is loosely attached. Let r' = Al(r) be the digraph of alternet of r. It follows from [10, Lemmas 3.1-3.3] that r' is a connected asymmetric digraph of out-valence 4 and that G = Aut(r'). It also follows easily that an automorphism which is semiregular on r' is also semiregular on r.
Note that |V(r' )| = |V(r)|/4 and hence we may apply the induction hypothesis to r' to conclude that it has a non-identity semiregular automorphism g. Together with the observation in the previous sentence, this concludes the proof.	□
3 Proof of Theorem 1.2
Let r be an arc-transitive graph of valency 8. We must show that r has a non-identity semiregular automorphism.
Clearly, we may assume that r is connected. Let G = Aut(r). If r is locally-quasiprimitive then the result follows from Theorem 1.1. We therefore assume that Gi(v) is not quasiprimitive. By Lemma 2.4, Gr(v) is a {2,3}-group and hence, by Lemma 2.5, so is Gv. We may also assume that G itself is a {2,3}-group and hence it is solvable by Burnside's Theorem.
It follows that G has an elementary abelian minimal normal subgroup N. If N has at most two orbits then the result follows from Lemma 2.2. We may thus assume that N has at least three orbits and, in particular, Nr(v) is intransitive. If N is semiregular then the conclusion follows. We may thus assume that Nv = 1 and hence N^^ = 1. In particular, r/N has valency strictly less than 8 and N^^ is anon-trivial, intransitive normal subgroup
34
Ars Math. Contemp. 8 (2015) 133-148
of cl{v). Since the orbits of Nr(v) are blocks of it follows that Nr(v) is a 2-group and hence N is an elementary abelian 2-group. Let K be the kernel of the action of G on N-orbits.
If r/N is 4-valent then v is adjacent to at most two vertices from any N-orbit. It follows that Kr(v) is a 2-group and hence so are Kv and K. If |V(T/N)| is a power of 2 then so is |V(r)| and the result follows from Lemma 2.1. We may thus assume that |V(T/N)| is not a power of 2 and, by Lemma 2.6, G/K contains a semiregular element of odd order. It then follows from Lemma 2.3 that G contains a semiregular element of odd order.
It remains to deal with the case when r/N is 2-valent. In this case, there is a natural orientation of r as a connected asymmetric 4-valent digraph r and Aut(r) is a subgroup of index 2 in G. By Theorem 2.7, Aut(r) has a semiregular element. This concludes the proof.
Acknowledgements. We thank the anonymous referees for their valuable advice. References
[1]	E. Dobson, A. Malnic, D. Marusic and L. A. Nowitz, Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Combin. Theory, Ser. B 97 (2007), 371-380.
[2]	E. Dobson, A. Malnic, D. Marusic and L. A. Nowitz, Minimal normal subgroups of transitive permutation groups of square-free degree, Discrete Math. 307 (2007), 373-385.
[3]	E. Dobson and D. Marusic, On semiregular elements of solvable groups, Comm. Algebra 39 (2011), 1413-1426.
[4]	M. Giudici and G. Verret, Semiregular automorphisms in arc-transitive graphs of valency 2p, in preparation.
[5]	M. Giudici and J. Xu, All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism, J. Algebraic Combin. 25 (2007), 217-232.
[6]	K. Kutnar and D. Marusic, Recent Trends and Future Directions in Vertex-Transitive Graphs, Ars. Math. Contemp. 1 (2008), 112-125.
[7]	D. Marusic, On vertex symmetric digraphs, Discrete Math. 36 (1981), 69-81.
[8]	D. Marusic and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, European J. Combin. 19 (1998), 707-712.
[9]	P. M. Neumann, Finite Permutation Groups, edge-coloured graphs and matrices, in: M. P. J. Curran (ed.), Topics in groups theory and computations, Academic Press, London (1977).
[10]	P. Potocnik and G. Verret, On the vertex-stabiliser in arc-transitive digraphs, J. Combin. Theory, Ser. B 100 (2010), 497-509.
[11]	C. E. Praeger, Imprimitive symmetric graphs, Ars Combin. 19 (1985), 149-163.
[12]	H. Wielandt, Finite permutation groups, translated from German by R. Bercov, Academic Press, New York (1964).
[13]	J. Xu, Semiregular automorphisms of arc-transitive graphs with valency pq, European J. Com-bin. 29 (2008), 622-629.