¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 179-186
https://doi.org/10.26493/1855-3974.1894.37c
(Also available at http://amc-journal.eu)
Arc-transitive graphs of valency twice a prime admit a semiregular automorphism*
Michael Giudici1 ©
Department of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia
Gabriel Verret * ©
Department of Mathematics, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Received 1 January 2019, accepted 16 February 2020, published online 15 October 2020
Abstract
We prove that every finite arc-transitive graph of valency twice a prime admits a nontrivial semiregular automorphism, that is, a non-identity automorphism whose cycles all have the same length. This is a special case of the Polycirculant Conjecture, which states that all finite vertex-transitive digraphs admit such automorphisms.
Keywords: Arc-transitive graphs, polycirculant conjecture, semiregular automorphism. Math. Subj. Class. (2020): 20B25, 05E18
1 Introduction
All graphs in this paper are finite. In 1981, Marusic asked if every vertex-transitive digraph admits a nontrivial semiregular automorphism [13], that is, an automorphism whose cycles all have the same length. This question has attracted considerable interest and a generalisation of the affirmative answer is now referred to as the Polycirculant Conjecture [4]. See [1] for a recent survey on this problem.
One line of investigation of this question has been according to the valency of the graph or digraph. Every vertex-transitive graph of valency at most four admits such an automorphism [7, 14], and so does every vertex-transitive digraph of out-valency at most three [9].
*	Authors are grateful to the anonymous referees for their helpful suggestions.
^The research of the first author was supported by the ARC Discovery Project DP160102323.
*	Gabriel Verret is grateful to the N.Z. Marsden Fund for its support (via grant UOA1824).
E-mail addresses: michael.giudici@uwa.edu.au (Michael Giudici), g.verret@auckland.ac.nz (Gabriel Verret)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
106
Ars Math. Contemp. 18 (2020) 105-115
Every arc-transitive graph of prime valency has a nontrivial semiregular automorphism [10] and so does every arc-transitive graph of valency 8 [17]. Partial results were also obtained for arc-transitive graphs of valency a product of two primes [18]. We continue this theme by proving the following theorem.
Theorem 1.1. Arc-transitive graphs of valency twice a prime admit a nontrivial semiregular automorphism.
2	Preliminaries
If G is a group of automorphisms of a graph r and v is a vertex of r, we denote by Gv the stabiliser in G of v, by r(v) the neighbourhood of v, and by G^(v) the permutation group induced by Gv on r(v). We will need the following well-known results.
Lemma 2.1. Let r be a connected graph and G < Aut(r). If a prime p divides |Gv | for some v G V(r), then there exists u G V(r) such that p divides |G^(u) |.
Proof. Since p divides |Gv |, there exists an element g of order p in Gv. As g = 1, there are vertices not fixed by g. Among these vertices, let w be one at minimal distance from v. Let P be a path of minimal length from v to w and let u be the vertex preceding w on P. By the definition of w, we have that u is fixed by g, so g G GU. On the other hand, g does not fix the neighbour w of u, so gr(u) = 1 hence |gr(u) | = p and the result follows. □
Lemma 2.2. Let G be a permutation group and let K be a normal subgroup of G such that G/K acts faithfully on the set of K-orbits. If G/K has a semiregular element Kg of order r coprime to |K |, then G has a semiregular element of order r.
Proof. See for example [17, Lemma 2.3].	□
Lemma 2.3. A transitive group of degree a power of a prime p contains a semiregular element of order p.
Proof. In a transitive group of degree a power of a prime p, every Sylow p-subgroup is transitive. A non-trivial element of the center of this subgroup must be semiregular. □
Recall that a permutation group is quasiprimitive if every non-trivial normal subgroup is transitive, and biquasiprimitive if it is transitive but not quasiprimitive and every nontrivial normal subgroup has at most two orbits.
3	Arc-transitive graphs of prime valency
In the most difficult part of our proof, the arc-transitive graph of valency twice a prime will have a normal quotient with prime valency. We will thus need a lot of information about arc-transitive graphs of prime valency, which we collect in this section. We start with the following result, which is [3, Theorem 5]:
Theorem 3.1. Let r be a connected G-arc-transitive graph of prime valency p such that the action of G on V(r) is either quasiprimitive or biquasiprimitive. Then one of the following holds:
(1) G contains a semiregular element of odd prime order;
M. Giudici and G. Verret: Arc-transitive graphs of valency twice a prime
181
(2)	|V(r)| is a power of 2;
(3)	r = K12, G = M11 and p = 11;
(4)	|V(r)| = (p2 — 1)/2s and G = PSL2(p) or PGL2(p), where p is a Mersenne prime and s is a proper divisor of (p —1)/2 but also a multiple of the product of the distinct prime divisors of (p — 1)/2;
(5)	|V(r)| = (p2 — 1)/s and G = PGL2(p), where p and s are as in part (4), and r is the canonical double cover of the graph given in (4).
(Recall that the canonical double cover of a graph r is r x K2.) We note that in cases (4) and (5), we must have p > 127, since this is the smallest Mersenne prime p such that (p — 1)/2 is not squarefree. This fact will be used at the end of Section 4.
Corollary 3.2. Let r be a connected G-arc-transitive graph of prime valency. Then one of the following holds:
(1)	G contains a semiregular element of odd prime order;
(2)	|V(r)| is a power of 2;
(3)	G contains a normal 2-subgroup P such that (r/P, G/P) is one of the graph-group pairs in (3-5) of Theorem 3.1.
Proof. Suppose that | V(r) | is not a power of 2. If G is quasiprimitive or biquasiprimitive on V(r), then the result follows immediately from Theorem 3.1 (with P =1 in case (3)). We thus assume that this is not the case and let P be a normal subgroup of G that is maximal subject to having at least three orbits on V(r). In particular, P is the kernel of the action of G on the set of P-orbits. Hence G/P acts faithfully, and quasiprimitively or biquasiprimitively on V(r/P). Since r has prime valency, is connected and G-arc-transitive, [12, Theorem 9] implies that P is semiregular. We may thus assume that P is a 2-group. (Otherwise P contains a semiregular element of odd prime order.) If G/P contains a semiregular element of odd prime order, then Lemma 2.2 implies that so does G. We may assume that this is not the case. Similarly, we may assume that |V(r/P)| is not a power of 2. (Otherwise, |V(r) | is a power of 2.) It follows that r/P and G/P are as is (3-5) of Theorem 3.1.	□
We will now prove some more results about the graphs that appear in (3-5) of Theorem 3.1. Let us first recall the notion of coset graphs. Let G be a group with a subgroup H and let g G G such that g2 G H but g G NG(H). The graph Cos(G, H, HgH) has vertices the right cosets of H in G, with two cosets Hx and Hy adjacent if and only if xy-1 G HgH. Observe that the action of G on the set of vertices by right multiplication induces an arc-transitive group of automorphisms such that H is the stabiliser of a vertex. Moreover, every arc-transitive graph can be constructed in this way [16, Theorem 2].
Lemma 3.3. The graphs in (3) and (4) of Theorem 3.1 have a 3-cycle.
Proof. Clearly K12 has a 3-cycle so suppose that r is one of the graphs given in (4). Let G be as in Theorem 3.1 and let v g V(r). Then G is one of PSL2(p) or PGL2(p) and acts arc-transitively on r. In both cases, let X = PSL2(p), so G = X or |G : X| =2. By [ , Lemma 5.3], we have that Gv = Cp x Cs if G = PSL2(p), and Cp x C2s if
106	Ars Math. Contemp. 18 (2020) 105-115
G = PGL2(p). By [ , pp. 285-286], PGL2(p) has a unique conjugacy class of subgroups of order p and the normaliser of such a subgroup is isomorphic to Cp x Cp-1, which is the stabiliser in PGL2(p) of a 1-dimensional subspace of the natural 2-dimensional vector space. The intersection of this subgroup with X is isomorphic to Cp x C(p-1)/2, which has odd order. It follows that if |G : X | =2, then Gv is not contained in X. Thus, in both cases, X is transitive on V(r). Since X is normal in G, Xv = 1 and r has prime valency, it follows that X is arc-transitive on r and so r = Cos(X, H, HgH) where H = Cp x Cs and g € X\NX (H) such that HgH is a union of p distinct right cosets of H.
Since H has a characteristic subgroup Y of order p, it follows that NX (H) normalises Y and so Nx(H) < Nx(Y) ^ Cp x C(p_1)/2. Since Nx(Y)/Y is cyclic it follows that NX(H) = NX(Y). Also note that NX(H) is the stabiliser in X of a 1-dimensional subspace and so the action of X on the set of right cosets of NX (H) is 2-transitive and the stabiliser of any two 1-dimensional subspaces is isomorphic to C(p-1)/2. Let x € X. The stabiliser in X of the coset Hx is Hx and so the orbit of Hx under H has length |H : H n Hx|. In particular, H fixes the coset Hx if and only if x € NX (H), and so H fixes |NX(H) : H| = (p(p - 1)/2)/ps = (p - 1)/2s points of V(r). Moreover, since the stabiliser of two 1-dimensional subspaces is isomorphic to C(p-1)/2 it follows that if x € NX(H) then H n Hx = C(p_1)/2 and so |H : H n Hx| = p. Thus the points of V(r) that are not fixed by H are permuted by H in orbits of size p and so for any g € NX (H) we have that HgH is a union of p distinct right cosets of H.
For each x € NX (H) define the bijection Ax of V(r) by Hy ^ x-1Hy = Hx-1y. Since X acts on V(r) by right multiplication, we see that Ax commutes with each element of X. Moreover, Ax is nontrivial if and only if x € H. Let C = {Ax | x € NG(H)} < Sym(V(r)). Since X acts transitively on V(r) and C centralises X, it follows from [6, Theorem4.2A] that C acts semiregularly on V(r). Now |C| = |NX(H) : H| = (p-1)/2s and X x C < Sym(V(r)). Since C < X x C, the set of orbits of C forms a system of imprimitivity for X x C and hence for X. Moreover, since C is semiregular, comparing orders yields that C has |V(r)|/|C| = p + 1 orbits. One of these orbits is the set of fixed points of H and H transitively permutes the remaining p orbits of C. In particular, it follows that C transitively permutes the nontrivial orbits of H and so the isomorphism type of r does not depend on the choice of the double coset HgH.
Let Z be the subgroup of scalar matrices in SL2 (p) and let H be the subgroup of the stabiliser in SL2(p) of the 1-dimensional subspace ((1,0)} such that H = H/Z. Note that
h = ^ ^ € H and let g = ^ ^ ^. In particular, letting h = hZ and g = gZ
we have that g € NX(H) and so we may assume that r = Cos(X, H, HgH). Now Hg and Hgh are both adjacent to H and one can check that g(gh)-1 = hgh € HgH and so {H, Hg, Hgh} is a 3-cyclein r.	□
Definition 3.4. Let r be a graph and let S0 be a subset of V(r). Let S = S0. If a vertex u outside S has at least two neighbours in S, add u to S. Repeat this procedure until no more vertices outside S have this property. If at the end of the procedure, we have S = V(r), then we say that r is dense with respect to S0.
It is an easy exercise to check that denseness is well-defined.
Corollary 3.5. Let r be a graph in (3) or (4) of Theorem 3.1 and let S0 = {u, v} be an edge of r. Then r is dense with respect to S0.
M. Giudici and G. Verret: Arc-transitive graphs of valency twice a prime
183
Proof. Since r is arc-transitive of prime valency p, the local graph at v (that is, the subgraph induced on r(v)) is a vertex-transitive graph of order p and thus vertex-primitive. By Lemma 3.3, r has a 3-cycle so the local graph has at least one edge and thus must be connected. It follows that, running the process described in Definition 3.4 starting at S — S0, eventually S will contain all neighbours of v. Repeating this argument and using connectedness of r yields the desired conclusion.	□
The following is immediate from Definition 3.4.
Lemma 3.6. Let r be a graph and S0 be a set of vertices such that r is dense with respect to S0. Then the canonical double cover of r, with vertex-set V(r) x {0,1}, is dense with respect to S0 x {0,1}.
Proof. Let Sj be the sequence of subsets of V(r) obtained when running the procedure from Definition 3.4 starting with S0 and ending with Sn for some n. Since r is dense with respect to S0, we have Sn = V(r). For i e {1,..., n}, let Vj — Sj \ Sj_i. (In other words, vi is the first vertex added to S0 to get Si, then v2 is added to Si to get S2, etc.)
Now, let r' — r x K2 be the canonical double cover of r and let S'0 — S0 x {0,1} C V(r'). We now run the procedure from Definition 3.4 starting at S'0. At the first step, we note that, since v1 was added to S0, it must have at least two neighbours in S0, say u1 and w1. It follows that both (v1,0) and (v1,1) also have at least two neighbours in S'0 (for example, (u1,1) and (w1,1), and (u1,0) and (w1,0), respectively). We thus add (v1,0) and (v1, 1) to S0 to get S1 — S0 U {(v1,0), (v1,1)}. Note that S1 — S1 x {0,1}. We then repeat this procedure, preserving the condition Sj — Sj x {0,1} at each iteration. At the end of this process, we have S^ — S„ x {0,1} — V(r) x {0,1} — V(r') and so r' is dense with respect to S0 x {0,1}.	□
4 Proof of Theorem 1.1
Let p be a prime, let r be an arc-transitive graph of valency 2p and let G = Aut(r). We may assume that r is connected. If G is quasiprimitive or bi-quasiprimitive, then G contains anontrivial semiregular element, by [8, Theorem 1.2] and [10, Theorem 1.4]. We may thus assume that G has a minimal normal subgroup N such that N has at least three orbits. In particular, r/N has valency at least 2.
If N is nonabelian, then G has a nontrivial semiregular element by [18, Theorem 1.1]. We may therefore assume that N is abelian and, in particular, N is an elementary abelian q-group for some prime q.
We may also assume that N is not semiregular that is, Nv = 1 for some vertex v. It follows from Lemma 2.1 that 1 =	< Gr(v). As r is G-arc-transitive, we have that
Gr(v) is transitive and so the orbits of all have the same size, either 2 or p. Since N is a q-group, this size is equal to q. Writing d for the valency of r/N, we have that either (d,q) = (2,p) or (d,q) = (p, 2).
If d = 2 and q = p, then it follows from [ , Theorem 1] that r is isomorphic to the graph denoted by C(p, r, s) in [15]. By [15, Theorem 2.13], Aut(C(p, r, s)) contains the nontrivial semiregular automorphism q defined in [15, Lemma 2.5].
We may thus assume that d = p and q = 2. In this case, if u is adjacent to v, then u has exactly 2 = 2p/d neighbours in vN. Let K be the kernel of the action of G on N-orbits. By the previous observation, the orbits of Kr(v) have size 2 and thus it is a 2-group. It follows from Lemma 2.1 that Kv is a 2-group and thus so is K = NKv
v •
106
Ars Math. Contemp. 18 (2020) 105-115
Now, G/K is an arc-transitive group of automorphisms of r/N, so we may apply Corollary 3.2. If G/K has a semiregular element of odd prime order, then so does G, by Lemma 2.2. If |V(T/N)| is a power of 2, then so is |V(T)| and, in this case, G contains a semiregular involution by Lemma 2.3. We may thus assume that we are in case (3) of Corollary 3.2, that is, G/K contains a normal 2-subgroup P/K such that (r/P, G/P) is one of the graph-group pairs in (3-5) of Theorem 3.1. Note that P is a 2-group. Let M be a minimal normal subgroup of G contained in the centre of P. Note that M is an elementary abelian 2-group. We may assume that M is not semiregular hence Mv = 1 and so by Lemma 2.1, MV(v) = 1. Moreover, |M| = 2 as otherwise Mv = M and we would deduce that M fixes each element of V(T), a contradiction. Since M is central in P, Mv fixes every vertex in vP.
Note that the G-conjugates of Mv must cover M, otherwise M contains a nontrivial semiregular element. By the previous paragraph, the number of conjugates of Mv is bounded above by the number of P-orbits, that is | V(r/P) |, so we have
|M| < |Mv||V(r/P)|.
Since r is connected and G-arc-transitive, there are no edges within P-orbits. As MV(v) = 1, there exists g G Mv such that w and wg are distinct neighbours of v. Let u be the other neighbour of w in vP. Since Mv fixes every element of vP it follows that u is also a neighbour of w and wg and so {v, w, u, wg} is a 4-cycle in r. Thus the graph induced between adjacent P-orbits is a union of C4's.
If x is a vertex and is a P-orbit adjacent to x, then there is a unique C4 containing x between xP and , and thus a unique vertex z antipodal to x in this C4. We say that z is the buddy of x with respect to . The set of buddies of v is equal to r2(v) n vP, which is clearly fixed setwise by Gv. Moreover, each vertex has the same number of buddies. Furthermore, since Gv transitively permutes the set of p P-orbits adjacent to vP, either v has a unique buddy or it has exactly p buddies.
If v has a unique buddy z, then r(v) = r(z), and so swapping every vertex with its unique buddy is a nontrivial semiregular automorphism. Thus it remains to consider the case where v has p buddies. We first prove the following.
Claim. If X is a subgroup of M that fixes pointwise both aP and , and cP is a P-orbit adjacent to both aP and , then X fixes cP pointwise.
Proof. Suppose that some x G X does not fix c. Now x fixes aP pointwise, so cx must be the buddy of c with respect to aP. Similarly, cx must be the buddy of c with respect to . These are distinct, which is a contradiction. It follows that X fixes c and, since X < M, also cP.	□
Let s > 1, let a = (v0,..., vs) be an s-arc of r and let a' = (v0,..., vs_i). Now |vsM"s-i | = 2, so |Mvs-1 : M„s-1„s | = 2 and |Ma : Ma| < 2. Applying induction yields that
|Mv0 : Ma| < 2s.	(4.1)
We first assume that r/P and G/P areas in (3) or (4) of Theorem 3.1. Let {u, v} be an edge of r. By the previous paragraph, we have |Mv : Muv | < 2. Recall that Mv fixes all vertices in vP, so Muv fixes all vertices in vPUuP. Combining the claim with Corollary 3.5
M. Giudici and G. Verret: Arc-transitive graphs of valency twice a prime
181
yields that Muv = 1 and thus |Mv | = 2. It follows that |M| < |Mv ||V(r/P)| so |M| < 2|V(r/P)|. Since M is minimal normal in G, it is an irreducible G-module over GF(2), of dimension at least two. In fact, since M is central in P, it is also an irreducible (G/P)-module. Since G/P is nonabelian simple or has a nonabelian simple group as an index two subgroup, this implies that M is a faithful irreducible (G/P)-module over GF(2). If G/P = Mu, then |M| > 210 [11, Theorem 8.1], contradicting |M| < 2 • 12 = 24. If G/P = PSL2(p) or PGL2(p) then by [ , Section VIII], |M| > 2(p-1)/2. Recall that p > 127 and so this contradicts |M| < 2(p2 - 1)/2s < p2 - 1.
Finally, we assume that r/P is in (5) of Theorem 3.1, that is, r/P is the canonical double cover of a graph r' which appears in (4) of Theorem 3.1. In particular, V(r/P) = V(r') x {0,1}. By Lemma 3.3, r' has a 3-cycle, say (u, v, w). By Corollary 3.5 and Lemma 3.6, r/P is dense with respect to {u, v} x {0,1}. Now, let
a = ((u, 0), (v, 1), (w, 0), (u, 1), (v, 0)).
Since a contains {u, v} x {0,1}, r/P is dense with respect to a. Note that a is a 4-arc of r/P. Let a be a 4-arc of r that projects to a. Since r/P is dense with respect to a, arguing as in the last paragraph yields Ma = 1. On the other hand, if v G V(r) is the the initial vertex of a, then by (4.1), we have |Mv : Ma| < 24 and thus |Mv | < 24. Since |M| < |Mv||V(r/P)| it follows that |M| < 24(p2 - 1)/s. As above, M is a faithful irreducible (G/P)-module over GF(2) of dimension at least two. Since G/P = PGL2(p) we have from [ ] that |M| > 2(p-1)/2, which again contradicts |M| < 24(p2 - 1)/s < 24(p2 - 1).
ORCID iDs
Michael Giudici © https://orcid.org/0000-0001-5412-4656 Gabriel Verret © https://orcid.org/0000-0003-1766-4834
References
[1]	M. Arezoomand, A. Abdollahi and P. Spiga, On problems concerning fixed-point-free permutations and on the polycirculant conjecture—a survey, Trans. Comb. 8 (2019), 15-40, doi: 10.22108/toc.2018.112665.1585.
[2]	R. Burkhardt, Die Zerlegungsmatrizen der Gruppen PSL(2,pf), J. Algebra 40 (1976), 75-96, doi:10.1016/0021-8693(76)90088-0.
[3]	T. C. Burness and M. Giudici, Permutation groups and derangements of odd prime order, J. Comb. Theory Ser. A 151 (2017), 102-130, doi:10.1016/j.jcta.2017.04.007.
[4]	P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marusic and L. A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc. (2) 66 (2002), 325-333, doi:10.1112/s0024610702003484.
[5]	L. E. Dickson, Linear Groups: With an Exposition of the Galois Field Theory, Dover Publications, New York, 1958.
[6]	J. D. Dixon and B. Mortimer, Permutation Groups, volume 163 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1996, doi:10.1007/978-1-4612-0731-3.
[7]	E. Dobson, A. Malnics, D. Marussics and L. A. Nowitz, Semiregular automorphisms of vertex-transitive graphs of certain valencies, J. Comb. Theory Ser. B 97 (2007), 371-380, doi:10.1016/ j.jctb.2006.06.004.
106
Ars Math. Contemp. 18 (2020) 105-115
[8]	M. Giudici, Quasiprimitive groups with no fixed point free elements of prime order, J. London Math. Soc. (2) 67 (2003), 73-84, doi:10.1112/s0024610702003812.
[9]	M. Giudici, L. Morgan, P. Potocnik and G. Verret, Elusive groups of automorphisms of digraphs of small valency, EuropeanJ. Combin. 46 (2015), 1-9, doi:10.1016/j.ejc.2014.11.004.
[10]	M. Giudici and J. Xu, All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism, J. Algebraic Combin. 25 (2007), 217-232, doi:10.1007/s10801-006-0032-5.
[11]	G. D. James, The modular characters of the Mathieu groups, J. Algebra 27 (1973), 57-111, doi:10.1016/0021-8693(73)90165-8.
[12]	P. Lorimer, Vertex-transitive graphs: symmetric graphs of prime valency, J. Graph Theory 8 (1984), 55-68, doi:10.1002/jgt.3190080107.
[13]	D. Marusic, On vertex symmetric digraphs, Discrete Math. 36 (1981), 69-81, doi:10.1016/ 0012-365x(81)90174-6.
[14]	D. Marusic and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, EuropeanJ. Combin. 19 (1998), 707-712, doi:10.1006/eujc.1997.0192.
[15]	C. E. Praeger and M. Y. Xu, A characterization of a class of symmetric graphs of twice prime valency, EuropeanJ. Combin. 10 (1989), 91-102, doi:10.1016/s0195-6698(89)80037-x.
[16]	G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426-438, doi:10.1007/ bf01304186.
[17]	G. Verret, Arc-transitive graphs of valency 8 have a semiregular automorphism, Ars Math. Contemp. 8 (2015), 29-34, doi:10.26493/1855-3974.492.37d.
[18]	J. Xu, Semiregular automorphisms of arc-transitive graphs with valency pq, European J. Combin. 29 (2008), 622-629, doi:10.1016/j.ejc.2007.04.008.