\documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.32}{22(3)}{2015} \usepackage{amsthm,amsmath,amssymb} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{construction}[theorem]{Construction} \newcommand{\Split}{\mathrm{Split}} \newcommand{\Merge}{\mathrm {M}} \newcommand{\PX}{\mathrm{PX}} \newcommand{\cT}{\mathcal {T}} \newcommand{\cR}{\mathcal {R}} \newcommand{\cF}{\mathcal {F}} \def\soc{{\rm soc}} \def\Aut{{\rm Aut}} \def\Sym{{\rm Sym}} \def\Cay{{\rm Cay}} \newcommand{\C}{\mathrm{C}} \newcommand{\D}{\mathrm{D}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\K}{\mathbf{K}} \newcommand{\M}{\mathrm{M}} \renewcommand{\S}{\mathrm{S}} \newcommand{\V}{\mathrm{V}} \newcommand{\ZZ}{\mathbb Z} \newcommand{\cC}{\mathcal {C}} \renewcommand{\wr}{\mathop{\mathrm{wr}}} \def\cent#1#2{{\bf C}_{{#1}}({{#2}})} \def\Zent#1{{\bf Z}({{#1}})} \title{\bf Semiregular automorphisms\\ of cubic vertex-transitive graphs\\ and the abelian normal quotient method} \author{Joy Morris\thanks{This work was supported in part by a grant from the Natural Science and Engineering Research Council of Canada.}\\ \small Department of Mathematics and Computer Science\\[-0.8ex] \small University of Lethbridge\\[-0.8ex] \small Lethbridge, AB. T1K 3M4, Canada\\ \small\tt joy.morris@uleth.ca\\ \and Pablo Spiga\\ \small Dipartimento di Matematica e Applicazioni \\[-0.8ex] \small University of Milano-Bicocca \\[-0.8ex] \small Via Cozzi 53, 20125 Milano, Italy\\ \small\tt pablo.spiga@unimib.it\\ \and Gabriel Verret\thanks{Supported by UWA as part of the Australian Research Council grant DE130101001. }\\ \small Centre for Mathematics of Symmetry and Computation \\[-0.8ex] \small The University of Western Australia \\[-0.8ex] \small 35 Stirling Highway, Crawley, WA 6009, Australia\\ %[-0.8ex] \small FAMNIT, University of Primorska \\[-0.8ex] \small Glagolja\v{s}ka 8, SI-6000 Koper, Slovenia\\ \small\tt gabriel.verret@uwa.edu.au} % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Nov 22, 2014}{Aug 18, 2015}{Sep 11, 2015}\\ \small Mathematics Subject Classifications: 20B25, 05E18} \begin{document} \maketitle \begin{abstract} We characterise connected cubic graphs admitting a vertex-transitive group of automorphisms with an abelian normal subgroup that is not semiregular. We illustrate the utility of this result by using it to prove that the order of a semiregular subgroup of maximum order in a vertex-transitive group of automorphisms of a connected cubic graph grows with the order of the graph. \end{abstract} \section{Introduction} All the graphs and groups considered in this paper are finite. A very useful tool in the theory of group actions on graphs is the \emph{normal quotient method (NQM)}. This is used to study (and possibly classify) a family of pairs $(\Gamma,G)$ having certain additional properties, where $\Gamma$ is a finite graph and $G$ is a subgroup of the automorphism group $\Aut(\Gamma)$ of $\Gamma$. (For example, the family consisting of the pairs $(\Gamma,G)$ where $\Gamma$ is a finite $G$-vertex-transitive graph.) The NQM has an impressive pedigree (for example, see~\cite{GLP,GXu,PNQ,PraegerPyber,PraegerSpigaV}). To use this method, one generally splits the analysis into two cases, as follows: \begin{enumerate} \item every nontrivial normal subgroup of $G$ is transitive; \label{caseQP} \item $G$ has a nontrivial intransitive normal subgroup $N$. \label{caseNQP} \end{enumerate} In case~\ref{caseQP}, $G$ is a \emph{quasiprimitive} group. These groups are classified (see~\cite{Praeger}) and have a very restricted structure. In many applications, this allows this case to be completely dealt with. The difficulty usually lies in case~\ref{caseNQP}. Here, one usually considers the quotient pair $(\Gamma/N,G/N)$ (see Section~\ref{notation} for the definition). Typically, this pair still lies in the family under consideration and, since $\Gamma/N$ is smaller than $\Gamma$, it is natural to try to use an inductive approach. However, it is often very difficult to recover information about $(\Gamma,G)$ from $(\Gamma/N,G/N)$. We now describe a variant of the NQM which is sometimes more successful, the \emph{abelian normal quotient method (ANQM)}. As before, one starts with a family of pairs $(\Gamma,G)$ to study but the analysis is usually split into three cases: \begin{enumerate} \item $G$ has no nontrivial abelian normal subgroups; \label{caseSS} \item $G$ has an abelian normal subgroup that is not semiregular; \label{caseAbNSemi} \item every abelian normal subgroup of $G$ is semiregular and $G$ has at least one such subgroup, say $N$.\label{caseAbSemi} \end{enumerate} The main advantage of the ANQM over the NQM lies in case~\ref{caseAbSemi}. Just as in case~\ref{caseNQP} of the NQM, one usually considers the quotient pair $(\Gamma/N,G/N)$, but the fact that $N$ is abelian and semiregular is often of tremendous help. The comparative disadvantage is that cases~\ref{caseSS} and~\ref{caseAbNSemi} of the ANQM are potentially more difficult than case~\ref{caseQP} of the NQM. For some problems this is an advantageous trade-off and many recent papers have used this approach (see for example \cite{Dobson,Li,PSV4valent,genlost,8valent}). We now explain why cases~\ref{caseSS} and~\ref{caseAbNSemi} of the ANQM are often manageable. In case~\ref{caseSS}, $G$ has trivial soluble radical. Such a group has some well-known properties: its socle is a direct product of nonabelian simple groups and the group acts faithfully on its socle by conjugation. In particular, the Classification of Finite Simple Groups can be brought to bear on the problem to obtain very detailed information. Similarly, the situation in case~\ref{caseAbNSemi} is surprisingly restrictive and very strong results can often be proved under this hypothesis. Consider, for example, the following theorem due to Praeger and Xu (the graphs which appear in the statement will be defined in Section~\ref{sec:PX}): \begin{theorem}[{{\cite[Theorem~$1$]{PraegerXu}}}]\label{PXu} Let $\Lambda$ be a connected $4$-valent $G$-arc-transitive graph. If $G$ has an abelian normal subgroup that is not semiregular then $\Lambda\cong \PX(2,r,s)$ for some $r\geq 3$ and $1\leq s\leq r-1$. \end{theorem} Clearly, Theorem~\ref{PXu} is very useful when applying the abelian normal quotient method to $4$-valent arc-transitive graphs, as it deals with case~\ref{caseAbNSemi} as satisfactorily as one could hope for, that is, giving a complete classification of the possible graphs. (For examples of applications, see~\cite{PSV4valent,genlost,Verret2}.) One of our goals is to prove the following analogue of Theorem~\ref{PXu} for cubic vertex-transitive graphs (the graphs which appear in Theorem~\ref{CubicPXu} will be defined in Section~\ref{sec:PX}): \begin{theorem}\label{CubicPXu} Let $\Gamma$ be a connected cubic $G$-vertex-transitive graph. If $G$ has an abelian normal subgroup that is not semiregular then $\Gamma$ is isomorphic to one of $\K_4$, $\K_{3,3}$, $\Q_3$ or $\S\PX(2,r,s)$ for some $r\geq 3$ and $1\leq s\leq r-1$. \end{theorem} Much like Theorem~\ref{PXu} with respect to $4$-valent arc-transitive graphs, Theorem~\ref{CubicPXu} will be very useful when applying the abelian normal quotient method to cubic vertex-transitive graphs. To illustrate this usefulness, we prove the following: \begin{theorem}\label{theorem:main1} There exists a function $f:\mathbb{N}\to \mathbb{N}$ satisfying $f(n)\rightarrow \infty$ as $n\rightarrow\infty$ such that, if $\Gamma$ is a connected $G$-vertex-transitive cubic graph of order $n$ then $G$ contains a semiregular subgroup of order at least $f(n)$. \end{theorem} Theorem~\ref{theorem:main1} settles positively the conjecture posed in~\cite[Problem~6.3]{CGJKKMN}. Note that, contrary to what is claimed in the statement of~\cite[Problem~6.3]{CGJKKMN}, the conjecture in~\cite[Problem BCC~17.12]{Cameron} (which also appeared in~\cite{CSS} as Conjecture~$2$) is actually stronger. Namely,~\cite[Problem BCC~17.12]{Cameron} strengthens~\cite[Problem~6.3]{CGJKKMN} by considering only cyclic semiregular subgroups. Despite the fact that~\cite[Problem~6.3]{CGJKKMN} has a positive solution,~\cite[Problem BCC~17.12]{Cameron} was recently shown to be false by the second author~\cite{SpigaCubic}. Note also that Theorem~\ref{theorem:main1} has appeared previously in~\cite{Li}, however the proof in that paper contains a critical mistake (in the proof of Claim~2, on the last page). In our proof of Theorem~\ref{theorem:main1} we do not make any effort to optimise or even keep track of the most rapidly growing function $f$ satisfying the hypothesis. Our current proof shows that $f(n)$ can be taken to be $\log(\log(n))$. However, we conjecture that this is far from best possible: \begin{conjecture}\label{conjec} There exists a constant $c>0$ such that in Theorem~\ref{theorem:main1} we can take $f(n)=n^{c}$. \end{conjecture} In some sense, Conjecture~\ref{conjec} is best possible as it was shown in~\cite{CSS} that $f(n)\leq n^{1/3}$, for infinitely many values of $n$. \subsection{Notation and structure of the paper}\label{notation} The notation used throughout this paper is standard. If $\Gamma$ is a graph and $u$ and $v$ are adjacent vertices of $\Gamma$ then $u$ and $v$ are \emph{neighbours} of each other and $(u,v)$ is an \emph{arc} of $\Gamma$. The set of neighbours of $v$ is called its neighbourhood and is denoted by $\Gamma(v)$. If $G\leq\Aut(\Gamma)$, we say that $\Gamma$ is \textit{$G$-vertex-transitive} (respectively, \textit{$G$-arc-transitive}) if $G$ acts transitively on the vertices (respectively, arcs) of $\Gamma$. The stabiliser of the vertex $v$ in $G$ is denoted by $G_v$ and $G_v^{\Gamma(v)}$ denotes the permutation group induced by $G_v$ in its action on $\Gamma(v)$. Let $\Gamma$ be a $G$-vertex-transitive graph and let $N$ be a normal subgroup of $G$. For every vertex $v$, the $N$-orbit containing $v$ is denoted by $v^N$. The \emph{normal quotient graph} $\Gamma/N$ has the $N$-orbits on $\V(\Gamma)$ as vertices, with an edge between distinct vertices $v^N$ and $w^N$ if and only if there is an edge of $\Gamma$ between $v'$ and $w'$, for some $v' \in v^N$ and some $w' \in w^N$. Note that $G$ has an induced transitive action on the vertices of $\Gamma/N$. Moreover, it is easily seen that the valency of $\Gamma/N$ is less or equal to the valency of $\Gamma$. The dihedral group of order $2r$ is denoted by $\D_r$. It is usually viewed as a permutation group on the set $\ZZ_r$ in a natural way. We also identify the regular cyclic subgroup of $\D_r$ with $\ZZ_r$. The remainder of our paper is divided as follows: in Section~\ref{sec:PX}, we define the graphs which appear in Theorems~\ref{PXu} and~\ref{CubicPXu}, prove some useful results about them, and prove Theorem~\ref{CubicPXu}. Theorem~\ref{theorem:main1} is proved in Section~\ref{sec:last}. \section{Praeger-Xu graphs and their split graphs}\label{sec:PX} We first define the graphs $\PX(2,r,s)$ and prove some useful results about them. \begin{definition} Let $r$ and $s$ be positive integers with $r\geq 3$ and $1\leq s\leq r-1$. The graph $\PX(2,r,s)$ has vertex-set $\ZZ_2^s\times\ZZ_r$ and edge-set $\{\{(n_0,n_1,\ldots,n_{s-1},x),(n_1,\ldots,n_{s-1},n_{s},x+1)\}\mid n_i\in \ZZ_2,x\in\ZZ_r\}$. \end{definition} Here is another description of these graphs that is more geometric and sometimes easier to work with. First, the graph $\PX(2, r, 1)$ is the lexicographic product of a cycle of length $r$ and an edgeless graph on two vertices. In other words, $\V(\PX(2, r, 1)) = \ZZ_2 \times \ZZ_r$ with $(u, x)$ being adjacent to $(v, y)$ if and only if $x - y \in \{-1, 1\}$. Next, a path in $\PX(2, r, 1)$ is called \emph{traversing} if it contains at most one vertex from $\ZZ_2 \times \{y\}$, for each $y \in \ZZ_r$. Finally, for $s \geq 2$, the graph $\PX(2, r, s)$ has vertex-set the set of traversing paths of $\PX(2, r, 1)$ of length $s - 1$, with two such paths being adjacent in $\PX(2, r, s)$ if and only if their union is a traversing path of length $s$ in $\PX(2, r, 1)$. It is not hard to see that this is equivalent to the original definition and that $\PX(2,r,s)$ is a connected $4$-valent graph with $r2^s$ vertices. Observe that there is a natural action of the wreath product $W:=\ZZ_2 \wr \D_r=\ZZ_2^r\rtimes\D_r$ as a group of automorphisms of $\PX(2, r, 1)$ with an induced faithful arc-transitive action on $\PX(2, r, s)$, for every $s\in\{1,\ldots,r-1\}$. Specifically, $W$ acts on $\V(\PX(2,r,s))=\ZZ_2^s\times\ZZ_r$ in the following way: for $g=(g_0,\ldots,g_{r-1},h)\in W$ (with $g_0,\ldots,g_{r-1}\in\ZZ_2$ and $h\in\D_r$), we have \[(n_0,n_1,\ldots,n_{s-1},x)^g=(n_0+{g_x},n_1+{g_{x+1}},\ldots,n_{s-1}+{g_{x+s-1}},x^h), \] where the subscripts are taken modulo $r$ and $x^h$ denotes the image of $x$ under $h$. We will also need the concept of an arc-transitive cycle decomposition, which was studied in some detail in~\cite{CycleDec}. \begin{definition}\label{def:cycledec} A \emph{cycle} in a graph is a connected regular subgraph of valency 2. A \emph{cycle decomposition} $\cC$ of a graph $\Lambda$ is a set of cycles in $\Lambda$ such that each edge of $\Lambda$ belongs to exactly one cycle in $\cC$. If there exists an arc-transitive group of automorphisms of $\Lambda$ that maps every cycle of $\cC$ to a cycle in $\cC$ then $\cC$ will be called \emph{arc-transitive}. \end{definition} \begin{construction}[{{\cite[Construction~$11$]{PSV1280}}}]\label{cons:split} The input of this construction is a pair $(\Lambda,\cC)$, where $\Lambda$ is a $4$-valent graph and $\cC$ is an arc-transitive cycle decomposition of $\Lambda$. The output is the graph $\Split(\Lambda,\cC)$, the vertices of which are the pairs $(v,C)$ where $v\in\V(\Lambda)$, $C\in\cC$ and $v$ lies on the cycle $C$, and two vertices $(v_1,C_1)$ and $(v_2,C_2)$ are adjacent if and only if either $C_1\neq C_2$ and $v_1=v_2$, or $C_1=C_2$ and $\{v_1,v_2\}$ is an edge of $C_1$. \end{construction} Note that $\Split(\Lambda,\cC)$ is a cubic graph. We now consider a very important cycle decomposition of $\PX(2,r,s)$: \begin{definition}\label{defdef} Let $\underline{n}=(n_1,\ldots,n_{s-1})\in \ZZ_2^{s-1}$, let $x\in \ZZ_r$ and let $C_{\underline{n},x}$ be the cycle of length four of $\PX(2,r,s)$ given by \[((0,\underline{n},x),(\underline{n},0,x+1),(1,\underline{n},x),(\underline{n},1,x+1)).\] Then $\cC:=\{C_{\underline{n},x}\mid \underline{n}\in \ZZ_2^{s-1},x\in\ZZ_r\}$ is a cycle decomposition of $\PX(2,r,s)$ into cycles of length four called the \emph{natural} cycle decomposition of $\PX(2,r,s)$. As the arc-transitive action of $\ZZ_2\wr \D_r$ on $\PX(2,r,s)$ induces a transitive action on $\cC$, we see that $\cC$ is arc-transitive. The graph $\Split(\PX(2,r,s),\cC)$ is simply denoted by $\S\PX(2,r,s)$. It is not hard to see that the graph $\S\PX(2,r,s)$ can also be described in the following way: its vertex-set is $\ZZ_2^s\times\ZZ_r\times\{+,-\}$ and its edge-set is \[\{\{(n_0,\ldots,n_{s-1},x,+),(n_1,\ldots,n_{s},x+1,-)\}\mid n_i\in \ZZ_2,x\in\ZZ_r\}~\cup\qquad\] \[\qquad \{\{(n_0,\ldots,n_{s-1},x,+),(n_0,\ldots,n_{s-1},x,-)\}\mid n_i\in \ZZ_2,x\in\ZZ_r\}.\] It is clear from this definition that the graph $\S\PX(2,r,s)$ is bipartite. Note also that if one contracts every edge of the form $\{(\underline{n},x,-),(\underline{n},x,+)\}$ in $\S\PX(2,r,s)$, one recovers $\PX(2,r,s)$. Observe that the wreath product $W:=\ZZ_2\wr\D_r=\ZZ_2^r\rtimes\D_r$ has a faithful action on $\V(\Gamma)=\ZZ_2^s\times\ZZ_r\times\{+,-\}$. Namely, for $g=(g_0,\ldots,g_{r-1},h)\in W$ (with $g_0,\ldots,g_{s-1}\in \ZZ_2$ and $h\in \D_r$), we have \[(n_0,n_1,\ldots,n_{s-1},x,\pm)^g= \begin{cases}(n_0+{g_x},n_1+{g_{x+1}},\ldots,n_{s-1}+{g_{x+s-1}},x^h,\pm) \textrm{ if } h\in\ZZ_r,\\ (n_0+{g_x},n_1+{g_{x+1}},\ldots,n_{s-1}+{g_{x+s-1}},x^h,\mp) \textrm{ otherwise,}\end{cases}\] where the subscripts are taken modulo $r$ and $x^h$ denotes the image of $x$ under $h$. It is easy to check that $W$ is a vertex-transitive group of automorphisms of $\S\PX(2,r,s)$. \end{definition} The graphs $\S\PX(2,r,s)$ have appeared before in the literature, see for example~\cite[Section~3]{Dobson} and~\cite[Corollary~1.5]{PSV4valent}. \begin{lemma}\label{boring} Up to conjugacy in $\Aut(\PX(2,r,s))$, the natural cycle decomposition of $\PX(2,r,s)$ is the unique arc-transitive cycle decomposition of $\PX(2,r,s)$ into cycles of length four. \end{lemma} \begin{proof} Let $\Lambda=\PX(2,r,s)$, let $W=\ZZ_2^r\rtimes\D_r$ and let $\cC$ be an arbitrary arc-transitive cycle decomposition of $\Lambda$ into cycles of length four. We show that $\cC$ is conjugate to the natural cycle decomposition of $\Lambda$ under $\Aut(\Lambda)$. Suppose first that $r\neq 4$. In this case, we actually prove that $\cC$ is the natural cycle decomposition. By~\cite[Theorem~2.13]{PraegerXu}, we have $\Aut(\Lambda)=W$. Let $\pi$ be the canonical projection from $\V(\Lambda)=\ZZ_2^s\times\ZZ_r$ to $\ZZ_r$. Suppose that, for every $C\in\cC$, we have $|\pi(C)|= 2$. Let $C\in\cC$ and write $C=(v_0,v_1,v_2,v_3)$ with $v_0,v_1,v_2,v_3\in \V(\Lambda)$. Then $\pi(C)=\{x,x+1\}$ for some $x\in \ZZ_r$ and, replacing $(v_0,v_1,v_2,v_3)$ by $(v_1,v_2,v_3,v_0)$ if necessary, we may assume that $\pi(v_0)=\pi(v_2)=x$ and $\pi(v_1)=\pi(v_3)=x+1$. Thus $v_0=(n_0,n_1,\ldots,n_{s-1},x)$, $v_1=(n_1,n_2,\ldots,n_{s},x+1)$, $v_2=(1-n_0,n_1,\ldots,n_{s-1},x)$ and $v_3=(n_1,\ldots,n_{s-1},1-n_s,x+1)$, for some $n_0,\ldots,n_s\in\ZZ_2$. Let $\underline{n}=(n_1,\ldots,n_{s-1})$. There are now four cases to consider. If $n_0=n_s=0$ then $(v_0,v_1,v_2,v_3)=C_{\underline{n},x}$. If $n_0=0$ and $n_s=1$ then $(v_0,v_3,v_2,v_1)=C_{\underline{n},x}$. If $n_0=1$ and $n_s=0$ then $(v_2,v_1,v_0,v_3)=C_{\underline{n},x}$. Finally, if $n_0=n_s=1$ then $(v_2,v_3,v_0,v_1)=C_{\underline{n},x}$. In all cases we find that $C=C_{\underline{n},x}$. Since $C$ is an arbitrary element of $\cC$ we have shown that $\cC$ is the natural cycle decomposition of $\Lambda$. Suppose now that we have $|\pi(C)|\geq 3$ for some $C\in\cC$. In particular, $C$ contains a $2$-path $P$ such that $\pi(P)=(x,x+1,x+2)$ for some $x\in\ZZ_r$. Since $\cC$ is preserved by an arc-transitive group of automorphisms of $\Lambda$, there exists $g\in\Aut(\Lambda)$ such that $g$ acts on $C$ as a one-step rotation. As $\Aut(\Lambda)=W$, we have $g=(g_0,\ldots,g_{r-1},h)$, for some $g_0,\ldots,g_ {r-1}\in \ZZ_2$ and $h\in \D_r$. Up to replacing $g$ by its inverse, we may assume that $\pi(P^g)=(x+1,x+2,x+3)$. In particular, $h$ has order $r$. Since $C$ is a $4$-cycle and $r\neq 4$, this is a contradiction. If $r=4$ then $1\leq s\leq 3$ and there are only three graphs to consider: $\PX(2,4,1)$, $\PX(2,4,2)$ and $\PX(2,4,3)$. The statement can then be checked case-by-case, either by hand or with the assistance of a computer. \end{proof} We now introduce another construction which is, in some sense, an inverse to Construction~\ref{cons:split} (see Theorem~\ref{MergeTheorem}). \begin{construction}[{{\cite[Construction~$7$]{PSV1280}}}]\label{cons:merge} The input of this construction is a pair $(\Gamma,G)$, where $\Gamma$ is a cubic $G$-vertex-transitive graph such that $G_v^{\Gamma(v)}\cong\ZZ_2$. The output is a decomposition of the edge-set of $\Gamma$ into a perfect matching $\cT(\Gamma,G)$ and a union of cycles $\cR(\Gamma,G)$, as well as a graph $\Merge(\Gamma,G)$ and a partition $\cC(\Gamma,G)$ of the edges of $\Merge(\Gamma,G)$. Clearly, $G_v$ fixes exactly one neighbour of $v$, and hence each vertex $u\in\V(\Gamma)$ has a unique neighbour (which we will denote $u'$) with the property that $G_u=G_{u'}$. Observe that, for every $g\in G$ and every $v\in\V(\Gamma)$, we have $v''=v$ and $(v')^g=(v^g)'$. It follows that the set $\cT(\Gamma,G):=\{\{v,v'\} \colon v\in\V(\Gamma)\}$ is a $G$-edge-orbit forming a perfect matching of $\Gamma$. We define a new graph $\Merge(\Gamma,G)$, with vertex-set $\cT(\Gamma,G)$ and two elements $\{u,u'\}$ and $\{v,v'\}$ of $\cT(\Gamma,G)$ adjacent if and only if there is an edge in $\Gamma$ between $\{u,u'\}$ and $\{v,v'\}$; that is, if and only if there is a member of $\{u,u'\}$ adjacent to a member of $\{v,v'\}$ in $\Gamma$. Furthermore, since $G$ is vertex-transitive and $G_v$ has two orbits on $\Gamma(v)$ (one of them being $\{v'\}$ and the other one being $\Gamma(v)\setminus\{v'\}$), $G$ has exactly two arc-orbits, and, since $G$ is not edge-transitive, $G$ also has exactly two edge-orbits (one of them being $\cT(\Gamma,G)$). Since $\cT(\Gamma,G)$ forms a perfect matching, the other edge-orbit (which we will call $\cR(\Gamma,G)$) induces a subgraph isomorphic to a disjoint union of cycles, say $C_1,\ldots,C_n$. Finally, let $\iota$ be the map $$ \iota\colon\{u,v\} \mapsto \{\{u,u'\},\{v,v'\}\} $$ from $\cR(\Gamma,G)$ to the edge-set of $\Merge(\Gamma,G)$ and let $\cC(\Gamma,G)=\{\iota(C_1),\ldots,\iota(C_n)\}$. \end{construction} A \emph{circular ladder graph} is the Cartesian product of a cycle of length at least $3$ with a complete graph on $2$ vertices. When $n \geq 2$, the Cayley graph $\Cay(\ZZ_{2n},\{1,-1,n\})$ is called a \emph{M\"{o}bius ladder graph}. We collect a few results about Construction~\ref{cons:merge} which were proved in~\cite{PSV1280}. \begin{theorem}[{{\cite[Lemma~9, Theorems~$10$ and $12$]{PSV1280}}}]\label{MergeTheorem} Let $\Gamma$ be a connected cubic $G$-vertex-transitive graph such that $G_v^{\Gamma(v)}\cong\ZZ_2$. If $\Gamma$ is not isomorphic to a circular ladder graph or a M\"{o}bius ladder graph, then $\Merge(\Gamma,G)$ is a connected $4$-valent $G$-arc-transitive graph and $\cC(\Gamma,G)$ is an arc-transitive cycle decomposition of $\Merge(\Gamma,G)$. Moreover, $\Gamma=\Split(\Merge(\Gamma,G),\cC(\Gamma,G))$. \end{theorem} Let $\K_4$ denote the complete graph on $4$ vertices, $\K_{3,3}$ the complete bipartite graph with parts of size $3$ and $\Q_3$ the $3$-cube. We now prove Theorem~\ref{CubicPXu}, which we restate for convenience. \medskip \noindent\textbf{Theorem~\ref{CubicPXu}.}\emph{ Let $\Gamma$ be a connected cubic $G$-vertex-transitive graph. If $G$ has an abelian normal subgroup that is not semiregular then $\Gamma$ is isomorphic to one of $\K_4$, $\K_{3,3}$, $\Q_3$ or $\S\PX(2,r,s)$ for some $r\geq 3$ and $1\leq s\leq r-1$.} \begin{proof} Let $v\in\V(\Gamma)$, let $N$ be an abelian normal subgroup of $G$ that is not semiregular and let $p$ be a prime dividing $|N_v|$. Note that the subgroup of $N$ generated by the elements of order $p$ is elementary abelian, is not semiregular and is characteristic in $N$, and thus normal in $G$. In particular, replacing $N$ by this subgroup, we may assume that $N$ is an elementary abelian $p$-group. Note also that, as $N$ is abelian and not semiregular, $N$ is intransitive. Furthermore, since $\Gamma$ is cubic and connected, $G_v$ is a $\{2,3\}$-group, and hence $p\in\{2,3\}$. Suppose that $p=3$. Since $N$ is not semiregular, we have $N_v \neq 1$ hence $|N_v^{\Gamma(v)}|$ is divisible by $3$ and therefore $N_v^{\Gamma(v)}$ is transitive. Let $u\in \Gamma(v)$. Since $G$ is transitive on $\V(\Gamma)$, $N_u^{\Gamma(u)}$ is transitive hence every neighbour of $u$ is in $v^N$. Thus every vertex at distance $2$ from $v$ is in $v^N$. As $N$ is abelian, $N_v$ fixes $v^N$ pointwise and, since $N_v^{\Gamma(v)}$ is transitive, this implies that every neighbour of $v$ has the same neighbourhood. Therefore $\Gamma\cong\K_{3,3}$. Suppose that $p=2$. Since $N$ is not semiregular, we have $N_v\neq 1$ and hence $|N_v^{\Gamma(v)}|=2$. Since $N_v^{\Gamma(v)}$ is normal in $G_v^{\Gamma(v)}$ this implies that $G_v^{\Gamma(v)}\cong\ZZ_2$. Let $\cT(\Gamma,G)$, $\cR(\Gamma,G)$, $\M(\Gamma,G)$ and $\cC(\Gamma,G)$ be as in Construction~\ref{cons:merge}. Let $k$ be the length of the cycles in $\cR(\Gamma,G)$ (and thus also in $\cC(\Gamma,G)$). Let $\{u,v\}\in\cR(\Gamma,G)$, let $C$ be the cycle of $\Gamma - \cT(\Gamma,G)$ containing $u$ and $v$, and observe that $C$ is a block of imprimitivity for $G$ and hence also for $N$. Note that $N_u$ and $N_v$ act on $C$ as reflections fixing adjacent vertices. Therefore $\langle N_v,N_u\rangle$ fixes $C$ setwise, and the permutation group induced by $\langle N_v,N_u\rangle$ on $C$ is either $\D_k$ (when $k$ is odd) or $\D_{k/2}$ (when $k$ is even). Since $N$ is abelian, it follows that $k=4$. Suppose that $\Gamma$ is a circular ladder graph of order $2n$. If $n=4$ then $\Gamma\cong\Q_3$. We thus assume that $n\neq 4$. In particular, some edges are contained in a unique $4$-cycle while others are contained in more than one $4$-cycle. Call the latter \emph{rungs}. Since $G$ has two orbits on edges and the rungs form a perfect matching, $\cT(\Gamma,G)$ must be the set of rungs. This implies that $\Gamma - \cT(\Gamma,G)$ consists of two cycles of length $n$, contradicting the fact that $k=4$. Suppose now that $\Gamma$ is a M\"{o}bius ladder graph of order $2n$. If $n=2$ then $\Gamma\cong\K_4$ and if $n=3$ then $\Gamma\cong\K_{3,3}$. We thus assume that $n\geq 4$ and the same argument as in the last paragraph yields again that $\cT(\Gamma,G)$ is the set of edges that are contained in more than one $4$-cycle. The removal of these leaves a cycle of length $2n$, which is a contradiction. We may thus assume that $\Gamma$ is neither a circular ladder nor a M\"{o}bius ladder graph. By Theorem~\ref{MergeTheorem}, $\M(\Gamma,G)$ is a connected $4$-valent $G$-arc-transitive graph and $\cC(\Gamma,G)$ is an arc-transitive cycle decomposition of $\M(\Gamma,G)$ consisting of cycles of length $k=4$. Moreover $\Gamma\cong\Split(\M(\Gamma,G),\cC(\Gamma,G))$. Let $\{v,v'\}\in\cT(\Gamma,G)$. Note that $132$ for every $k$. By Theorem~\ref{CubicPXu}, it follows that $\Gamma_{k}$ is isomorphic to $\S\PX(2,r_k,s_k)$ for some $r_k\geq 5$ and $1\leq s_k\leq r_k-1$. Now, from Corollary~\ref{PX case} we get $r_k\leq c$ and hence $|\V(\Gamma_{k})|=2^{s_k}r_k\leq 2^{c-1}c$. This contradicts the fact that $\sup\{|\V(\Gamma_k)|\mid k\in\mathbb{N}\}=\infty$. \medskip \noindent\textbf{Case 3.} For every $k$, every abelian normal subgroup of $G_k$ is semiregular and $G_k$ has at least one such subgroup. \smallskip \noindent Replacing $\cF$ by a subfamily, we may assume that $|\V(\Gamma_k)|>2c$ for every $k$. Let $N_k$ be an abelian minimal normal subgroup of $G_k$. Note that $N_k$ is elementary abelian and semiregular and hence $|N_k|\leq c$. Since $|\V(\Gamma_k)|>2c$, it follows that $N_k$ has at least three orbits and, since $N_k\neq 1$, the graph $\Gamma_k/N_k$ has valency at most two and hence is a cycle of length $\ell_k:=|\V(\Gamma_k)|/|N_k|\geq |\V(\Gamma_k)|/c$. Let $K_k$ be the kernel of the action of $G_k$ on $N_k$-orbits and let $C_k$ be the centraliser of $N_k$ in $K_k$. As $N_k$ is abelian, we have $N_k\leq C_k$. Also, as $N_k$ and $K_k$ are normal in $G_k$, so is $C_k$. Since $N_k$ is abelian and $K_k$ preserves the $N_k$-orbits setwise, we must have $C_k^\Delta=N_k^\Delta$ for each $N_k$-orbit $\Delta$. It follows that the commutator $[C_k,C_k]$ fixes each $N_k$-orbit pointwise and hence $[C_k,C_k]=1$. Thus $C_k$ is abelian and hence semiregular. For $v\in \V(\Gamma_k)$, we have $K_k=N_k(K_k)_v$. As $N_k\leq C_k\leq K_k$, this implies that $C_k=N_k$, that is, $\cent {K_k}{N_k}=N_k$. Since $|N_k|\leq c$, we have $|G_k:\cent {G_k}{N_k}|\leq |\Aut(N_k)|\leq c!$. Thus $$|G_k/K_k:K_k\cent {G_k}{N_k}/K_k|\leq c!.$$ Recall that $G_k/K_k$ acts faithfully and vertex-transitively on the cycle $\Gamma_k/N_k$ of length $\ell_k$ and thus contains a rotation of order at least $\ell_k/2$. Since $|G_k/K_k:K_k\cent {G_k}{N_k}/K_k|\leq c!$, it follows that $\cent {G_k}{N_k}$ contains an element $g_k$ acting on $\Gamma_k/N_k$ as a rotation of order $r_k$ with $r_k\geq \ell_k/(2c!)$. Now, $g_k^{r_k}\in K_k\cap \cent {G_k}{N_k}=\cent {K_k}{N_k}=N_k$ and hence $g_k^{r_k}$ is semiregular. Since $g_k$ acts semiregularly on $\Gamma_k/N_k$, it follows that $g_k$ is semiregular. In particular, $\langle g_k\rangle$ is a semiregular subgroup of $G_k$ of order at least $r_k\geq\ell_k/(2c!) \geq|\V(\Gamma_k)|/(2cc!)$. Since $\sup\{|\V(\Gamma_k)|\mid k\in\mathbb{N}\}=\infty$, this is our final contradiction. \end{proof} \begin{thebibliography}{99} \bibitem{Cameron} P.~Cameron (ed.). \newblock Problems from the Seventeenth British Combinatorial Conference. \newblock {\em Discrete Math.} 231:469--478, 2001. \bibitem{CGJKKMN} P.~Cameron, M.~Giudici, G.~Jones, W.~Kantor, M.~Klin, D.~Maru\v{s}i\v{c}, L.~A.~Nowitz. \newblock Transitive permutation groups without semiregular subgroups. \newblock {\em J. London Math. Soc.} 66:325--333, 2002. \bibitem{CSS} P.~Cameron, J.~Sheehan, P.~Spiga. \newblock Semiregular automorphisms of vertex-transitive cubic graphs. \newblock {\em European J. Combin.} 27:924--930, 2006. \bibitem{Dobson} E.~Dobson, A.~Malni\v{c}, D.~Maru\v{s}i\v{c}, L.~A.~Nowitz. \newblock Semiregular automorphisms of vertex-transitive graphs of certain valencies. \newblock {\em J.\ Combin.\ Theory, Ser.\ B} 97:371--380, 2007. \bibitem{GLP} M.~Giudici, C.~H.~Li, C.~E.~Praeger. \newblock Analysing finite locally $s$-arc transitive graphs. \newblock {\em Trans. Amer. Math. Soc.} 356:291--317, 2004. \bibitem{GXu} M.~Giudici, J.~Xu. \newblock All vertex-transitive locally-quasiprimitive graphs have a semiregular automorphism. \newblock {\em J. Algebraic Combin.} 25:217--232, 2007. \bibitem{Li} C.~H.~Li. \newblock Semiregular automorphisms of cubic vertex-transitive graphs. \newblock {\em Proc. Amer. Math. Soc.} 136:1905--1910, 2008. \bibitem{CycleDec} \v{S}.~Miklavi\v{c}, P.~Poto\v{c}nik, S.~Wilson. \newblock Arc-transitive cycle decompositions of tetravalent graphs. \newblock {\em J. Combin. Theory Ser. B} 98:1181--1192, 2008. \bibitem{PSV4valent} P.~Poto\v{c}nik, P.~Spiga, G.~Verret. \newblock Bounding the order of the vertex-stabiliser in $3$-valent vertex-transitive and $4$-valent arc-transitive graphs. \newblock {\em J. Combin. Theory Ser. B} 111:148--180, 2015. \bibitem{PSV1280}P.~Poto\v{c}nik, P.~Spiga, G.~Verret. \newblock Cubic vertex-transitive graphs on up to $1280$ vertices. \newblock {\em J. Symbolic Comput.} 50:465--477, 2013. \bibitem{PNQ}C.~E.~Praeger. \newblock Imprimitive symmetric graphs. \newblock {\em Ars Combin.} 19 A:149--163, 1985. \bibitem{Praeger} C.~E.~Praeger. \newblock An O'Nan-Scott theorem for finite quasiprimitive permutation groups and an application to $2$-arc transitive graphs. \newblock {\em J. London Math. Soc.} 47:227--239, 1993. \bibitem{PraegerPyber}C.~E.~Praeger, L.~Pyber, P.~Spiga, E.Szab\'{o}. \newblock Graphs with automorphism groups admitting composition factors of bounded rank. \newblock {\em Proc. Amer. Math. Soc.} 140:2307--2318, 2012. \bibitem{PraegerSpigaV}C.~E.~Praeger, P.~Spiga, G.~Verret. \newblock Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph. \newblock {\em J. Combin. Theory Ser. B} 102:797--819, 2012. \bibitem{PraegerXu}C.~E.~Praeger, M.~Y.~Xu. \newblock A Characterization of a Class of Symmetric Graphs of Twice Prime Valency. \newblock {\em European J. Combin.} 10:91--102, 1989. \bibitem{SpigaCubic}P.~Spiga. \newblock Semiregular elements in cubic vertex-transitive graphs and the restricted Burnside problem. \newblock {\em Math. Proc. Cambridge Phil. Soc.} 157:45--61, 2014. \bibitem{genlost} P.~Spiga, G.~Verret. \newblock On the order of vertex-stabilisers in vertex-transitive graphs with local group $\C_p\times \C_p$ or $\C_p\wr\C_2$. \newblock {\em J. Algebra}, to appear. \bibitem{Verret2} G.~Verret. \newblock On the order of arc-stabilisers in arc-transitive graphs, II. \newblock {\em Bull. Austral. Math. Soc.} 87:441--447, 2013. \bibitem{8valent} G.~Verret. \newblock Arc-transitive graphs of valency $8$ have a semiregular automorphism. \newblock {\em Ars Math. Contemp.} 8:29--34, 2015. \end{thebibliography} \end{document}