\documentclass[12pt]{article} \usepackage{amsmath,amssymb} \usepackage{e-jc} \specs{P2.6}{25(2)}{2018} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\usepackage[margin=1.5cm]{geometry} %\usetikzlibrary{arrows,shapes,positioning,decorations.markings, decorations.pathreplacing,decorations.pathmorphing} \newcommand{\Cay}{\mathop{\mathrm{Cay}}} \newcommand{\Aut}{\mathop{\mathrm{Aut}}} \newcommand{\Sym}{\mathop{\mathrm{Sym}}} \newcommand{\Alt}{\mathop{\mathrm{Alt}}} \def\Zent#1{{\bf Z}({{#1}})} \def\cent#1#2{{\bf C}_{{#1}}({{#2}})} \def\o#1{{\bf o}({{#1}})} \def\Fitt#1{{\bf F}({{#1}})} \def\nor#1#2{{\bf N}_{{#1}}({{#2}})} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{prop}[theorem]{Proposition} %\theoremstyle{definition} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{notation}[theorem]{Notation} %\newtheorem{remark}[theorem]{Remark} \newtheorem{hypothesis}[theorem]{Hypothesis} \newcommand{\Orr}{\mathop{\mathrm{ORR}}} \dateline{Jun 15, 2017}{Mar 19, 2018}{Apr 13, 2018} \MSC{05C25, 05C20, 20B25} \Copyright{ The author. Released under the CC BY-ND license (International 4.0).} \title{On the existence of Frobenius \\digraphical representations} \author{Pablo Spiga\\ \small Dipartimento di Matematica e Applicazioni\\[-0.8ex] \small University of Milano-Bicocca\\[-0.8ex] \small 20162 Via Cozzi 55, Italy\\ \small\tt pablo.spiga@unimib.it} \begin{document} \maketitle \begin{abstract} A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A digraphical, respectively graphical, Frobenius representation, DFR and GFR for short, of a Frobenius group $F$ is a digraph, respectively graph, whose automorphism group as a group of permutations of the vertex set is $F$. The problem of classifying which Frobenius groups admit a DFR and GFR has been proposed by Mark Watkins and Thomas Tucker and is a natural extension of the problem of classifying which groups that have a digraphical, respectively graphical, regular representation. In this paper, we give a partial answer to a question of Mark Watkins and Thomas Tucker concerning Frobenius representations: ``All but finitely many Frobenius groups with a given Frobenius complement have a DFR''. %\noindent\textbf{Keywords} regular representation, Frobenius representation, Cayley digraph, automorphism group \end{abstract} %\begin{keyword} %regular representation \sep DRR \sep GRR \sep TRR \sep ORR \sep non-solvable group %\end{keyword} \section{Introduction}\label{s: intro} All groups and graphs in this paper are finite. Let $G$ be a group and let $S$ be a subset of $G$. The {\em Cayley digraph} $\Cay(G,S)$ over $G$ with connection set $S$ is the digraph with vertex set $G$ and with $(x,y)$ being an arc if $yx^{-1}\in S$. (In this paper, an {\em arc} is an ordered pair of adjacent vertices.) It is easy to see that the group $G$ acts faithfully as a group of automorphisms of $\Cay(G,S)$ via the right regular representation. In particular, Cayley digraphs offer a natural way to represent groups geometrically and combinatorially as groups of automorphisms of digraphs. Clearly, this representation is particularly meaningful if $G$ is the full automorphism group of $\Cay(G,S)$. In this context it is fairly natural to ask which groups $G$ admit a subset $S$ with $G$ being the automorphism group of $\Cay(G,S)$; that is, $\Aut(\Cay(G,S))=G$. In this case, we say that $G$ admits a {\em digraphical regular representation} (or DRR for short). Babai~\cite[Theorem~$2.1$]{babai1} has given a complete classification of the groups admitting a DRR. In light of Babai's result, it is natural to try to combinatorially represent groups as automorphism groups of special classes of Cayley digraphs. Observe that if $S$ is inverse-closed (that is, $S=\{s^{-1}\mid s\in S\}:=S^{-1}$), then $\Cay(G,S)$ is undirected. Now, we say that $G$ admits a {\em graphical regular representation} (or GRR for short) if there exists an inverse-closed subset $S$ of $G$ with $\Aut(\Cay(G,S))=G$. With a considerable amount of work, starting with the pioneer work of Imrich~\cite{ Imrich1,Imrich2,Imrich3} and culminating in~\cite{Godsil, Hetzel}, the groups admitting a GRR have been completely classified. We recall that a {\em tournament} is a digraph $\Gamma:=(V,A)$ with vertex set $V$ and arc set $A$ such that, for every two distinct vertices $x,y\in V$, exactly one of $(x,y)$ and $(y,x)$ is in $A$. After the completion of the classification of DRRs and GRRs, Babai and Imrich~\cite{babai2} proved a classification of the finite groups admitting a {\em tournament regular representation} (or TRR for short). Much more recently, the subject of regular representations has discovered a new vitality in a number of different directions. First, answering a question of Babai~\cite[Problem 2.7]{babai1}, Morris and the author of this paper have classified in~\cite{morrisspiga,morrisspiga2,me2} the groups admitting an \emph{oriented regular representation} (or ORR for short): an oriented graph is a digraph with no digons. Second, various researchers have tried to represent some special classes of groups as DRR (or GRR) of very small valency, see for instance~\cite{Spiga,XF} and the bibliography therein. Third, motivated by the previous work, Conder, Doyle, Tucker and Watkins~\cite{WT,WT1} have considered a new intriguing variation on the theme: \emph{graphical Frobenius representations}. A \textit{Frobenius group} $F$ is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A \textit{graphical Frobenius representation} (GFR for short) of the Frobenius group $F$ is a graph whose automorphism group, as a group of permutations of the vertex set, is $F$. The definition of digraphical Frobenius representation (DFR for short) is given analogously. The Frobenius group $F$ is the semidirect product $N\rtimes H$, where $N$ is the nilpotent kernel of $F$ and $H$ is a Frobenius complement of $H$, and the action of $F$ is permutation isomorphic to the natural ``affine" action of $F$, with the group $N$ acting via its right regular representation and with $H$ acting on $N$ via conjugation. Now, $F$ admits a DFR (or GFR) whenever there exists a subset $S$ of $N$ ($S$ inverse-closed in the case of GFR) with $F=\Aut(\Cay(N,S))$. Despite its appearance, the problem of classifying the Frobenius groups admitting a DFR or a GFR is rather different from the classification of DRR, GRR, TRR and ORR. Indeed, the rich and highly restricted algebraic structure of Frobenius groups comes preponderantly into play. In~\cite{WT1}, the authors conjecture that ``All but finitely many Frobenius groups with a given Frobenius complement have a GFR''. In this paper we give a strong answer to the directed version of this conjecture. \begin{theorem}\label{thrm: main} There exists a function $f:\mathbb{N}\to\mathbb{N}$ such that, if $F$ is a finite Frobenius group with complement $H$ and with $|F|\ge f(|H|)$, then $F$ admits a $\mathrm{DFR}$. \end{theorem} Our function $f$ is rather explicit, see Section~\ref{sec : 4} and Remark~\ref{r : 12}, but very likely not best possible. At this point, it is also worth noting that various researchers have shown that for certain families of groups, almost all Cayley graphs are GRRs, or almost all Cayley digraphs are DRRs~\cite{BaGo,Dobson2,DSV,Godsil,MSV}. We prove an analogous result for DFR. \begin{theorem}\label{thrm: main1} Let $H$ be a finite group and let $\mathcal{H}$ be the family of all Frobenius groups $N\rtimes H$ with Frobenius kernel $H$. For every $\varepsilon>0$, there exists $n_\varepsilon\in\mathbb{N}$ such that, for every $N\rtimes H\in \mathcal{H}$ with $|N|\ge n_\varepsilon$, we have $$\frac{|\{S\subseteq N\mid F<\mathrm{Aut}(\mathrm{Cay}(N,S))\}|}{|\{S\subseteq N\mid F\le\mathrm{Aut}(\mathrm{Cay}(N,S))\}|}<\varepsilon.$$ \end{theorem} Roughly speaking, Theorem~\ref{thrm: main1} says that, when $N\rtimes H$ is a Frobenius group and $|N|$ is large compared to $|H|$, then a random $H$-invariant subset $S$ of $N$ gives rise to the DFR $\Cay(N,S)$.\footnote{ During the refereeing process of this manuscript, the author developing the ideas in this paper has given a positive solution to the GFR conjecture proposed by Conder, Doyle, Tucker and Watkins~\cite{WT,WT1}.} We prove a result analogous to Theorem~\ref{thrm: main1} for unlabeled Cayley graphs in Section~\ref{sec:6}. \section{Babai--Godsil estimates: first reduction}\label{BG} The argument in this section is completely inspired and in part taken from~\cite[Section~$4$]{BaGo}. For most of the arguments in this section we could simply refer to~\cite[Section~$4$]{BaGo}, however the hypothesis there are slightly different from our current needs. Therefore, rather than pointing out which parts in~\cite[Section~4]{BaGo} need to be refined (and how to refine them), for the sake of completeness we make this section self-contained and we repeat part of the results in~\cite[Section~4]{BaGo}. Henceforth, let $F:=N\rtimes H$ be a Frobenius group with kernel $N$ and complement $H$ acting on $\{1,\ldots,n\}$, where $n:=|N|$. As usual, $N$ acts regularly on $\{1,\ldots,n\}$ and the action of $H$ on $\{1,\ldots,n\} $ is permutation equivalent to the action of $H$ on $N$ by conjugation. Let $K$ denote a non-trivial proper normal subgroup of $F$ contained in $N$. Let $k:=|K|$ and $b:=[N:K]=n/k$. We let $\gamma_1,\ldots,\gamma_b$ be coset representatives of $K$ in $N$. Moreover, we choose $\gamma_1:=1$ to be the identity in $N$. Observe that $N/K$ defines a structure of group on $\{1,\ldots,b\}$ by setting $ij=k$ for every $i,j,k\in \{1,\ldots,b\}$ with $\gamma_i K\gamma_j K=\gamma_k K$. Write $v_0:=1$ where $v_0$ has to be understood as a point in the $N$-set $\{1,\ldots,n\}$. For each $i\in \{1,\ldots,b\}$, set $\mathcal{O}_i:={v_0}^{\gamma_iK}$. Observe that the $\mathcal{O}_i$s are the orbits of $K$ on $\{1,\ldots,n\}$, the group $K$ acts regularly on $\mathcal{O}_i$ and $|\mathcal{O}_i|=|K|=k$. For a subset $S$ of $N$, we let $\Cay(N,S)$ be the Cayley digraph of $N$ with connection set $S$. %We assume that %$$F\le \Aut(\Gamma)$$ We denote by $A_S$ the largest subgroup of $\Aut(\Cay(N,S))$ which normalizes $K$ and under which each orbit of $K$ is invariant. In symbols we have $$A_S:=\{g\in\nor {\Aut(\Cay(N,S))}K\mid \mathcal{O}_i^g=\mathcal{O}_i,\textrm{ for each }i\in \{1,\ldots,b\}\}.$$ The subscript $S$ in $A_S$ will make the notation cumbersome to use, but it constantly emphases that the definition of ``$A$'' depends on $S$, because so does $\Cay(N,S)$. The subgroup $A_S$ of $A$ depends also on the normal subgroup $K$ of $F$ and hence, in principle, we should use a double subscript for denoting $A_S$: however, for not making the notation too cumbersome to use, we have decided to drop this subscript because the dependency of $A_S$ upon $K$ (although very important) it is less relevant than the dependency of $A_S$ upon $S$. For a subgroup $Y$ of $\Sym(n)$ and a $Y$-invariant subset $X$ of $\{1,\ldots,n\}$, we write $Y\mid_{ X}$ for the restriction of $Y$ to $X$, that is, the image of the natural homomorphism $Y\to \Sym(X)$. For $i\in\{1,\ldots, b\}$, set $S_i:=S\cap \mathcal{O}_i$ and let $A_S^i:=(A_S)_{v_0}\mid_{\mathcal{O}_i}$ denote the restriction to $\mathcal{O}_i$ of the stabilizer $(A_S)_{v_0}$ in $A_S$ of the point $v_0\in\mathcal{O}_1$. In Lemmas~\ref{lemma41} and~\ref{lemma42} we use the notation established here. \begin{lemma}{{{\rm (See~\cite[Lemma $4.1$]{BaGo}.)}}}\label{lemma41} If none of the $S_i$, $i\in \{2,\ldots,b\}$, is invariant under any non-identity element of the group $A_S^i$, then $A_S=K$. \end{lemma} \begin{proof} Recall that the definition of $A_S$ depends on $S$ and on $K$. Clearly, $K\leq A_S$ and, since $K$ is transitive on $\mathcal{O}_1$, from the Frattini argument we obtain $A_S=(A_S)_{v_0}K$. Fix $i\in \{2,\ldots,b\}$. Let $f\in (A_S)_{v_0}$. Since $f\in \Aut(\Cay(N,S))$, we have $S^f=S$ and, since $f$ fixes every $K$-orbit setwise, we have $S_i^f=S_i$. Therefore, by hypothesis, the permutation $f$ restricted to $\mathcal{O}_i$ is the identity. Since this holds for each $i\in \{2,\ldots,b\}$, we get that $f$ fixes pointwise ${\{1,\ldots,n\}\setminus \mathcal{O}_1}$. Since this holds for every element $f\in (A_S)_{v_0}$, we see that $(A_S)_{v_0}$ fixes pointwise $\{1,\ldots,n\}\setminus \mathcal{O}_1$. In particular, $(A_S)_{v_0}\leq (A_S)_{v_0^{\gamma_2}}$ and, as $(A_S)_{v_0}$ and $(A_S)_{v_0^{\gamma_2}}$ have the same order, $(A_S)_{v_0}=(A_S)_{v_0^{\gamma_2}}$. Finally, as $(A_S)_{v_0}$ fixes pointwise $\{1,\ldots,n\}\setminus\mathcal{O}_1$, we get that $((A_S)_{v_0})^{\gamma_2}=(A_S)_{v_0^{\gamma_2}}=(A_S)_{v_0}$ fixes pointwise $(\{1,\ldots,n\}\setminus\mathcal{O}_1)^{\gamma_2}=\{1,\ldots,n\}\setminus\mathcal{O}_2$. Thus $(A_S)_{v_0}$ fixes pointwise $\{1,\ldots,n\}$ and $(A_S)_{v_0}=1$. Therefore $A_S=(A_S)_{v_0}K=K$. \end{proof} In what follows we use repeatedly the following facts. \begin{remark}\label{rem : 1}{\rm \begin{enumerate} \item Let $X$ be a finite group. Since a chain of subgroups of $X$ has length at most $\log_2|X|$, $X$ has a generating set of cardinality at most $\lfloor \log_2|X|\rfloor\le \log_2|X|$. \item Let $X$ be a finite group. Any automorphism of $X$ is uniquely determined by the image of the elements of a generating set for $X$. Therefore $|\Aut(X)|\le |X|^{\log_2|X|}=2^{(\log_2|X|)^2}$. \item Let $g$ be a permutation of the finite set $\Omega$ and set $\Delta:=\{\omega\in \Omega\mid \omega^g=\omega\}$. Then $g$ fixes each point of $\Delta$ and the cycles of $g$ on $\Omega\setminus \Delta$ have length at least $2$. Therefore $g$ fixes setwise at most $2^{|\Delta|+\frac{|\Omega\setminus\Delta|}{2}}$ subsets of $\Omega$. In particular, if $|\Delta|\le |\Omega|/2$, then $g$ fixes setwise at most $2^{\frac{3}{4}|\Omega|}$ subsets of $\Omega$. \item The subsets $S$ of $N$ with $F\le \Aut(\Cay(N,S))$ are exactly the $H$-invariant subsets of $N$. Since $H$ has a unique orbit of cardinality $1$ (namely $\{1\}$) and all other orbits have cardinality $|H|$, we see that there are exactly $2^{1+\frac{|N|-1}{|H|}}$ subsets $S$ of $N$ with $F\le \Aut(\Cay(N,S))$. \end{enumerate}} \end{remark} In the following lemma we slightly generalize and we make the estimates in the statement of~\cite[Lemma $4.2$]{BaGo} more explicit. \begin{lemma}{{\rm (See~\cite[Lemma $4.2$]{BaGo}.)}}\label{lemma42} For each $i\in \{2,\ldots,b\}$, we have $$|\{S\subseteq N\mid F\le \Aut(\Cay(N,S))\textrm{ and there exists }f\in (A_S)_{v_0} \textrm{ with }f\mid_{\mathcal{O}_i}\neq 1\}|\leq M'$$ where $M'=\max\left\{2^{1+\frac{n-1}{|H|}-\left(\frac{\sqrt{n}}{4}-(\log_2 n)^2\right)},2^{1+\frac{n-1}{|H|}-\left(\frac{\sqrt{n}-1-|H|}{|H|(1+2|H|)}\log_2(4/3)-2\log_2\sqrt{n}+1\right)}\right\}.$ \end{lemma} \begin{proof} First of all, recall that the definition of $A_S$ depends on $S$ and on $K$. Fix $i\in \{2,\ldots,b\}$ and denote by $\Phi_i$ the set $$\{S\subseteq N\mid F\le \Aut(\Cay(N,S)) \textrm{ and there exists }f\in (A_S)_{v_0} \textrm{ with }f\mid_{\mathcal{O}_i}\neq 1\}.$$ We follow the proof in~\cite[Lemma~$4.2$]{BaGo} without assuming that $N$ has odd order and taking into account the action of $H$ on $N$ by conjugation. We divide the proof in two cases. \medskip \noindent\textsc{Case 1: }$k\geq \sqrt{n}$. \smallskip \noindent Let $L^i$ denote the normalizer in $\Sym(\mathcal{O}_i)$ of $K^i:=K\mid_{\mathcal{O}_i}$. The group $K^i$ acts regularly, and hence so does its centralizer in $\Sym(\mathcal{O}_i)$. Therefore $L^i$ is isomorphic to a subgroup of the holomorph $K\rtimes \Aut(K)$ of $K$ and hence $$|L^i|\leq |K||\Aut(K)|< k\cdot k^{\log_2 k }.$$ Using $k\le n/2$, it is immediate to prove that $k\cdot k^{\log_2 k }0$. Moreover, a subset $S_{ji^{-1}}$ of $\mathcal{O}_{ji^{-1}}$ with $|S_{ji^{-1}}\cap S_j^{k_u^{-1}\gamma_i^{-1}}|\equiv |S_{ji^{-1}}\cap S_j^{k_v^{-1}\gamma_i^{-1}}|\pmod 2$ can be written as $X\cup Y$, where $X$ is as an arbitrary subset of $\mathcal{O}_{ji^{-1}}\setminus S_j^{n_v^{-1}\gamma_i^{-1}}$ and $Y$ is a subset of $S_j^{n_v^{-1}\gamma_i^{-1}}\setminus S_j^{n_u^{-1}\gamma_i^{-1}}$ of size having parity uniquely determined by the parity of $|X|$. Therefore we have $2^{k-(a-b)}2^{(a-b)-1}=2^{k-1}$ choices for $S_{ji^{-1}}$. Altogether we have \begin{eqnarray*} A&=& x\cdot 2^k+y\cdot 2^{k-1}=x2^k+2^{2k-1}-x2^{k-1}=2^{2k-1}+x2^{k-1}\\ &\leq& 2^{2k-1}+2^{k/2}2^{k-1}=2^{2k}\left(\frac{1}{2}+\frac{1}{2^{k/2+1}}\right)\leq 2^{2k}\left(\frac{1}{2}+\frac{1}{2^2}\right)=\frac{3}{4}\cdot 2^{2k} \end{eqnarray*} and~\eqref{eq6+} is proved. \smallskip We now consider an auxiliary digraph $X$: \begin{itemize} \item the vertices of $X$ are the $H$-orbits on $N/K=\{1,\ldots,b\}$ which are different from the orbit $\{1\}$ and the orbit $i^H$, \item the arcs of $X$ are the ordered pairs $(j_1^H,j_2^H)$ (where $j_1^H$ and $j_2^H$ are vertices) such that, there exist $j_1'\in j_1^H$ and $j_2'\in j_2^H$ with $j_2'=j_1'i^{-1}$. \end{itemize} Observe that $X$ is a directed graph. As each $H$-orbit has cardinality $|H|$, $X$ has maximum in-valency and maximum out-valency at most $|H|$ and hence the valency of the underlying undirected graph of $X$ is at most $2|H|$. Observe also that $X$ has no isolated vertices. Indeed, assume that $j^H$ is an isolated vertex. This means that for each $j'\in j^H$ the element $j'i^{-1}$ lies in $j^H$. This yields that $j^H$ is closed by the right multiplication by $i^{-1}$ and hence $j^H$ has cardinality divisible by the order of $i$; however, $|H| $ and $|i|$ are relatively prime because so are $|H|$ and $|N|$. As customary, let $\alpha:=\alpha(X)$ be the independence number of $X$ and let $j_1^H,\ldots,j_\alpha^H$ be an independent set of $X$ of cardinality $\alpha$. Since $X$ has $(b-1-|H|)/|H|$ vertices, a classical graph theoretic result of Caro-Tur\'an-Wei~\cite{11,40,41} yields that $X$ has an independent set of cardinality at least $$\frac{(b-1-|H|)/|H|}{1+2|H|}=\frac{b-1-|H|}{|H|(1+2|H|)};$$ therefore, $\alpha\ge (b-1-|H|)/(|H|(1+2|H|))$. Define $J:=\{j_1,\ldots,j_\alpha\}$. Given two distinct elements $u,v$ in $\mathcal{O}_i$, define $\Psi_i(u,v,J):=\bigcap_{j\in J}\Psi_i(u,v,j)$. Observe that, from~\eqref{eq6++} and from the fact that $\{j_1^{H},\ldots,j_\alpha^H\}$ is an independent set in $X$, the events $\{\Psi_i(u,v,j)\}_{j\in J}$ are pairwise independent. Thus, it follows from~\eqref{eq6+} that $$|\Psi_i(u,v,J)|\leq \left(\frac{3}{4}\right)^{\alpha}2^{1+\frac{n-1}{|H|}}\le \left(\frac{3}{4}\right)^{\frac{b-1-|H|}{|H|(1+2|H|)}}2^{1+\frac{n-1}{|H|}}.$$ We are now ready to conclude the proof of this lemma. Let $S\in \Phi_i$ and let $f\in (A_S)_{v_0}$ with $f\mid_{\mathcal{O}_i}\neq 1$. Let $u$ and $v$ be distinct vertices of $\Cay(N,S)$ in $\mathcal{O}_i$ with $u^f=v$. Since $f$ fixes $v_0$ and fixes setwise every $K$-orbit, we get $(\sigma(S,u,j))^f=\sigma(S,u^f,j)=\sigma(S,v,j)$, for every $j\in \{2,\ldots,b\}$ and hence (in particular) $S\in \Psi_i(u,v,J)$. Therefore, given $u$ and $v$, we have $|\Psi_i(u,v,J)|\leq (3/4)^{(b-1-|H|)/(|H|(1+2|H|))}2^{1+(n-1)/|H|}$ choices for $S$. As we have ${k\choose 2}$ choices for $\{u,v\}$ and as $b>\sqrt{n}$, we have \begin{eqnarray*} |\Phi_i|&\leq& {k\choose 2}\left(\frac{3}{4}\right)^{\frac{b-1-|H|}{|H|(1+2|H|)}}2^{1+\frac{n-1}{|H|}}<2^{2\log_2 \sqrt{n}-1}2^{\frac{\sqrt{n}-1-|H|}{|H|(1+2|H|)}\log_2(3/4)}2^{1+\frac{n-1}{|H|}} \end{eqnarray*} and the lemma follows. \end{proof} We are now ready to state the first reduction theorem. \begin{theorem}\label{red1} Let $F:=N\rtimes H$ be a Frobenius group with kernel $N$ and complement $H$. The number of subsets $S$ of $N$ with $F\le \Aut(\Cay(N,S))$ and such that there exists \begin{itemize} \item a non-trivial proper normal subgroup $K$ of $N$ and \item an automorphism $f\in \Aut(\Cay(N,S))$ normalizing $K$, with $f\notin N$ and with $f$ fixing setwise every $K$-orbit \end{itemize} is at most $2^{(\log_2 |N| )^2}(|N|/2-1)M'$, where $$M':=\max\left\{2^{1+\frac{n-1}{|H|}-\left(\frac{\sqrt{n}}{4}-(\log_2 n )^2\right)},2^{1+\frac{n-1}{|H|}-\left(\frac{\sqrt{n}-1-|H|}{|H|(1+2|H|)}\log_2(4/3)-2\log_2 \sqrt{n}+1\right)}\right\}.$$ \end{theorem} \begin{proof} Write $n:=|N|$. Every subgroup of $N$ has at most $\log_2 n$ generators and hence $N$ has at most $n^{\log_2 n}=2^{(\log_2 n)^2}$ subgroups. In particular, we have at most $2^{(\log_2 n)^2}$ choices for a non-trivial proper normal subgroup $K$ of $N$. Now, fix such a normal subgroup $K$, and let $S\subseteq N$ such that there exists $g\in \Aut(\Cay(N,S))\setminus N$ normalizing $K$ and fixing setwise every $K$-orbit. Thus $g\in A_S\setminus N$: recall that the definition of $A_S$ depends on $S$ and on $K$. Moreover, replacing $g$ by $gr^{-1}$, for a suitable $r\in N$ if necessary, we may assume that $g$ fixes the vertex $v_0\in \mathcal{O}_1$, that is, $g\in (A_S)_{v_0}\setminus \{1\}$. Now, we use the notation established in Lemmas \ref{lemma41} and \ref{lemma42}. Suppose that there exists $i\in \{2,\ldots,b\}$ and $f\in (F_S)_{v_0}$ with $f\mid_{\mathcal{O}_i}\neq 1$. Then, by Lemma~\ref{lemma42}, we have at most $(b-1)M'$ choices for $S$. (Observe that the factor $b-1$ accounts for the number of choices for $i\in \{2,\ldots,b\}$). Next suppose that $(A_S)\mid_{\mathcal{O}_i}=1$, for every $i\in \{2,\ldots,b\}$. Now, Lemma~\ref{lemma41} gives $A_S=N$ and hence $(A_S)_{v_0}=1$, contradicting our choice of $S$. Since $b\le n/2$, this proves that the number of choices for $S$ is at most \[2^{(\log_2 n)^2}\cdot (n/2-1)\cdot M'.\qedhere\] \end{proof} \section{Counting automorphisms: second reduction}\label{sec : 2} \begin{lemma}\label{l : -1} Let $F:=N\rtimes H$ be a Frobenius group with kernel $N$ and complement $H$ and let $\varphi\in \Aut(N)$ with $\varphi\notin H$. The number of subsets $S$ of $N$ with $\langle\varphi,F\rangle\le \Aut(\Cay(N,S))$ is at most $$ 2^{ \frac{3}{4}\frac{|N|}{|H|}-\frac{1}{2|H|}+\frac{1}{2}+\sqrt{|N|}\frac{|H|-1}{2|H|}}.$$ \end{lemma} \begin{proof} Let $\mathcal{S}:=\{n\in N\mid n^\varphi\in n^H\}$, where as usual $n^H:=\{n^h\mid h\in H\}$ is the $H$-orbit containing $n$. We may write $\mathcal{S}$ as the union $\mathcal{S}=\bigcup_{h\in H}\mathcal{S}_h$ where $\mathcal{S}_h:=\{n\in N\mid n^\varphi=n^h\}$. Observe that $\mathcal{S}_h=\{n\in N\mid n^{ h\varphi^{-1}}=n\}=\cent N{h\varphi^{-1}}$, for every $h\in H$. Now, let $h_1$ and $h_2$ be two distinct elements from $H$ and let $n\in \mathcal{S}_{h_1}\cap \mathcal{S}_{h_2}$. As $n^{h_1\varphi^{-1}}=n=n^{h_2\varphi^{-1}}$, we obtain $n=n^{h_1\varphi^{-1}(h_2\varphi^{-1})^{-1}}=n^{h_1h_2^{-1}}$. Since $1\ne h_1h_2^{-1}\in H$ and $F=N\rtimes H$ is a Frobenius group, $h_1h_2^{-1}$ centralizes no non-identity element of $N$; thus $n=1$ and $\mathcal{S}_{h_1}\cap\mathcal{S}_{h_2}=\{1\}$. This shows that \begin{equation}\label{eq : 1} |\mathcal{S}|=\left|\bigcup_{h\in H}\cent N{h\varphi^{-1}}\right|=\sum_{h\in H}|\cent N{h\varphi^{-1}}|-|H|+1. \end{equation} Let $\mathcal{C}:=\{n\in N\mid \varphi \textrm{ fixes setwise }n^H\}$. If $n\in \mathcal{C}$, then $(n^H)^\varphi=n^H$ and hence $n^\varphi\in n^H$, that is, $n\in \mathcal{S}$. Therefore $\mathcal{C}\subseteq \mathcal{S}$. Observe that $\mathcal{C}$ is $\varphi$-invariant and $H$-invariant. Indeed, if $n\in \mathcal{C}$, then $n^{\varphi}\in n^H$ and hence there exists $\bar{h}\in H$ with $n^\varphi=n^{\bar{h}}$. Now, $(n^\varphi)^H=(n^{\bar{h}})^H=n^H$ and hence $\varphi$ fixes setwise $(n^\varphi)^H$; thus $n^\varphi\in\mathcal{C}$. Moreover, if $h\in H$, then $(n^h)^H=n^H$; hence $\varphi$ fixes setwise $(n^h)^H$ and so $n^h\in\mathcal{C}$. Let $S$ be a subset of $N$ with $\langle \varphi,F\rangle\le \Aut(\Cay(N,S))$. Write $S:=S_1\cup S_2$, where $S_1:=S\cap\mathcal{C}$ and $S_2:=S\cap (N\setminus \mathcal{C})$. From the previous paragraph, $S_1$ and $S_2$ are both $\langle \varphi,H\rangle$-invariant. To obtain an upper bound on the number of such subsets $S$, we obtain separately two upper bounds on the number of possibilities for $S_1$ and $S_2$. Since $H$ acts as a Frobenius complement on $N$, the number of $H$-orbits in $\mathcal{C}$ is $$1+\frac{|\mathcal{C}|-1}{|H|}$$%\le 1+\frac{|\mathcal{S}|-1}{|H|}=\sum_{h\in H}\frac{|\cent N {\varphi h^{-1}}|}{|H|}$$ and hence we have at most $2^{1+\frac{|\mathcal{C}|-1}{|H|}}$ %$2^{\sum_{h\in H}|\cent N{\varphi h^{-1}}|/|H|}$ possibilities for $S_1$. (The summand ``$1$" accounts for the orbit $\{1\}$ of $H$ in its action on $N$.) To obtain an upper bound on the number of possibilities for $S_2$, we construct an auxiliary graph $\Gamma$: the vertices of $\Gamma$ are the $H$-orbits contained in $N\setminus \mathcal{C}$ and two $H$-orbits $n^H$ and $n'^H$ are declared to be adjacent if there exist $n_1\in n^H$ and $n_2\in n'^H$ such that $n_1^\varphi=n_2$. Observe that $\Gamma$ has no isolated vertices because, by definition of $\mathcal{C}$, no $H$-orbit contained in $N\setminus\mathcal{C}$ is $\varphi$-invariant. Indeed, if $n^H$ is contained in $N\setminus\mathcal{C}$ (that is, it is not contained in $\mathcal{C}$), then there exists $h\in H$ with $(n^h)^\varphi\notin (n^h)^H=n^H$. Therefore $n^H$ and $((n^h)^\varphi)^H$ are two distinct $H$-orbits adjacent in $\Gamma$. Next, observe that for the subset $S_2$ to be both $\varphi$- and $H$-invariant, $S_2$ must be a union of connected components of $\Gamma$. As $\Gamma$ has at most $|N\setminus \mathcal{C}|/{2|H|}$ connected components (because each connected component consists of at least two vertices), we have at most $2^{\frac{|N|-|\mathcal{C}|}{2|H|}}$ choices for $S_2$. Summing up, the number of possibilities for $S$ is at most \begin{equation*} 2^{1+\frac{|\mathcal{C}|-1}{|H|}}2^{\frac{|N|-|\mathcal{C}|}{2|H|}}= 2^{1-\frac{1}{|H|}+\frac{|N|}{2|H|}+\frac{|\mathcal{C}|}{2|H|}} \le 2^{1-\frac{1}{|H|}+\frac{|N|}{2|H|}+\frac{|\mathcal{S}|}{2|H|}}. \end{equation*} Now, using Eq.~\eqref{eq : 1}, we deduce that the number of possibilities for $S$ is at most \begin{equation}\label{eq: 2} 2^{\frac{1}{2}\left(\frac{|N|-1}{|H|}+1+\sum_{h\in H}\frac{|\cent N{h\varphi^{-1}}|}{|H|}\right)}. \end{equation} For each $h\in H$, define $d_h:=[N:\cent N{h\varphi^{-1}}]$ and $d:=\min(d_h\mid h\in H)$. Observe that $d\ge 2$ because $\varphi\notin H$. Fix $h_0\in H$, with $d_{h_0}=d$. Let $h\in H\setminus \{h_0\}$ and recall that $\cent N{h_0\varphi^{-1}}\cap \cent N {h\varphi^{-1}}=1$ because $\mathcal{S}_{h_0}\cap\mathcal{S}_h=1$. It follows that the mapping $\pi:N\to N/\cent N{h_0\varphi^{-1}}\times N/\cent N{h\varphi^{-1}} $ defined by $n\mapsto (n\cent N{h_0\varphi^{-1}},n\cent N{h\varphi^{-1}})$ is injective. (Observe that this mapping is not necessarily a group homomorphism because $\cent N{h\varphi^{-1}}$ is not necessarily a normal subgroup of $N$.) Therefore $|N|\le d_{h_0}d_h=dd_h$; hence $$\frac{1}{d_h}\le \frac{d}{|N|},$$ for every $h\in H\setminus\{h_0\}$. Suppose first that $d\ge\sqrt{|N|}$. Then \begin{eqnarray}\label{eq : 33} \sum_{h\in H}\frac{|\cent N{h\varphi^{-1}}|}{|H|}&=&\frac{|N|}{|H|}\sum_{h\in H}\frac{|\cent N{h\varphi^{-1}}|}{|N|}=\frac{|N|}{|H|}\sum_{h\in H}\frac{1}{d_h}\nonumber\\ &\le&\frac{|N|}{|H|}\sum_{h\in H}\frac{1}{d}=\frac{|N|}{d}\le \sqrt{|N|}. \end{eqnarray} The proof, in this case, follows from~\eqref{eq: 2} and~\eqref{eq : 33} and an easy computation. Suppose then that $d<\sqrt{|N|}$. Thus \begin{eqnarray}\label{eq : 3} \sum_{h\in H}\frac{|\cent N{h\varphi^{-1}}|}{|H|}&=&\frac{|N|}{|H|}\sum_{h\in H}\frac{|\cent N{h\varphi^{-1}}|}{|N|}=\frac{|N|}{|H|}\sum_{h\in H}\frac{1}{d_h}=\frac{|N|}{|H|}\left(\frac{1}{d}+\sum_{h\in H\setminus\{h_0\}}\frac{1}{d_h}\right)\nonumber\\\nonumber &\le&\frac{|N|}{|H|}\left(\frac{1}{d}+(|H|-1)\frac{d}{|N|}\right)\le \frac{|N|}{|H|}\left(\frac{1}{d}+\frac{|H|-1}{\sqrt{|N|}}\right)\nonumber\\ &\le& \frac{|N|}{|H|}\left(\frac{1}{2}+\frac{|H|-1}{\sqrt{|N|}}\right). \end{eqnarray} Now the proof, in this case, follows from~\eqref{eq: 2} and~\eqref{eq : 3}. \end{proof} \begin{corollary}\label{c : 1}Let $F$ be a Frobenius group with kernel $N$. Then the number of subsets $S$ of $N$ such that $$F<\nor {\Aut(\Cay(N,S))} N$$ is at most $$2^{\frac{3}{4}\frac{|N|}{|H|}-\frac{1}{2|H|}+\frac{1}{2}+\sqrt{|N|}\frac{|H|-1}{2|H|}+(\log_2 |N| )^2}.$$ \end{corollary} \begin{proof} Let $S$ be a subset of $N$ and set $A:=\Aut(\Cay(N,S))$. Suppose that $F<\nor A N$. As $N$ is transitive on the vertices of $\Cay(N,S)$, there exists $\varphi\in \nor A N\setminus F$ with $1^\varphi$. In particular, the action of $\varphi$ on the vertices of $\Cay(N,S)$ (that is, on $N$) is a group automorphism. Thus $\varphi\in \Aut(N)$. As $\varphi\notin H$, from Lemma \ref{l : -1}, we have at most $2^{\frac{3}{4}\frac{|N|}{|H|}-\frac{1}{2|H|}+\frac{1}{2}+\sqrt{|N|}\frac{|H|-1}{2|H|}}$ choices for $S$. Since $|\Aut(N)|< |N|^{\log_2|N|}=2^{(\log_2|N|)^2},$ we have at most $2^{(\log_2|N|)^2}$ choices for $\varphi$ and hence the result immediately follows. \end{proof} \section{Tools from the theory of primitive groups}\label{sec:primitive} We gather some results on primitive groups that will be useful in our problem. We start with a basic observation. \begin{lemma}\label{l : 0} Let $G$ be a Frobenius group with kernel $N$. Then every normal subgroup of $G$ either is contained in $N$ or contains $N$. \end{lemma} \begin{proof} Let $X$ be a normal subgroup of $G$ and suppose that $X\nleq N$. Then there exists $x\in X\setminus N$. Observe that $x$ acts by conjugation fixed-point-freely on $N\setminus\{1\}$. Therefore $N=[N,x]$, where $[N,x]$ is the commutator subgroup of $N$ and $x$. As $X\lhd G$ and $x\in X$, we get $N=[N,X]\le X$. \end{proof} As customary, given a group $X$, we denote by $\Fitt X$ the Fitting subgroup of $X$, that is, the largest normal nilpotent subgroup of $X$. Suppose that $G$ is a Frobenius group with Frobenius kernel $N$. Using the fact that $N$ is nilpotent, it is easy to prove that $\Fitt {G}=N$. In particular, the Frobenius kernel and the Frobenius complement are uniquely determined by $G$ as an abstract group. \begin{lemma}\label{l : 00} Let $G$ be an almost simple primitive group on $\Omega$ with socle $T$ and let $\omega\in \Omega$. If the point stabilizer $G_\omega$ is a Frobenius group as an abstract group, then $T_\omega=T\cap G_\omega$ is not contained in the Frobenius kernel $\Fitt{G_\omega}$ of $G_\omega$. \end{lemma} \begin{proof} We argue by contradiction and we suppose that $T_\omega\le \Fitt{G_\omega}$. Let $p$ be a prime dividing the order of $|T_\omega|$ and let $Q$ be a Sylow $p$-subgroup of $T_\omega$. Since $T_\omega$ is nilpotent, $Q$ is characteristic in $G_\omega$; hence $\nor G Q\ge G_\omega$. As $G_\omega$ is maximal in $G$, we deduce $\nor G {Q}=G_\omega$ and hence $T_\omega=T\cap G_\omega=T\cap \nor G {Q}=\nor T {Q}$. As $T_\omega$ is nilpotent, we deduce $\nor T {Q}=Q\cent T{Q}$. Since $T$ is a non-abelian simple group, from~\cite[Corollary $1.2$]{GMN} and from $\nor T Q=Q\cent T Q$, we get $p=2$. Since $p$ was an arbitrary prime number dividing the order of $T_\omega$, we obtain that $T_\omega$ is a $2$-group and that $T_\omega$ is self-normalizing in $T$. Thus $T_\omega$ is a Sylow $2$-subgroup of $T$. Since $T_\omega\le \Fitt{G_\omega}$ has even order and $G_\omega$ is a Frobenius group, the Frobenius complement of $G_\omega$ has odd order and hence $G_\omega$ is a solvable group. Therefore $G$ is an almost simple group with solvable point stabilizers. All pairs $(X,Y)$, with $X$ an almost simple group and with $Y$ a maximal solvable subgroup of $X$, are classified by Li and Zhang~\cite[Tables~$14$--$20$]{LZ}. Therefore, $(G,G_\omega)$ is one of the pairs classified by Li and Zhang. A careful and tedious (but not hard) case-by-case analysis on the tables in~\cite{LZ} reveals that, in our context, no example $(G,G_\omega)$ arises. In using these tables there are two facts that can be useful. First, $T$ cannot be an alternating or a sporadic simple group: in fact, for these groups $[G:T]$ is a power of $2$, but $[G:T]=[G_\omega:T_\omega]$ cannot be a power of $2$ because $[G_\omega:T_\omega]$ must be divisible by an odd prime being $G_\omega$ a Frobenius group. Second, the intersection $G_\omega \cap T=T_\omega$ is a $2$-group. \end{proof} Via the O'Nan-Scott theorem and its refinements~\cite{ONAN}, finite primitive permutation groups may be subdivided into eight classes, namely HA, HS, HC, SD, CD, TW, PA and AS, such that every primitive group belongs to exactly one of these types. For terminology regarding the types of primitive groups, we refer to~\cite{ONAN}. \begin{lemma}\label{l : 1} Let $G$ be a finite primitive group on $\Omega$. If $G_\omega$ is a Frobenius group as an abstract group, then $G$ has type $\mathrm{HA}$ or $\mathrm{AS}$. \end{lemma} \begin{proof} We use the structure of finite primitive groups, as described in~\cite{ONAN}. If $G$ is of type HS, HC, SD or CD, then $G_\omega$ contains a normal subgroup isomorphic to a direct product of non-abelian simple groups. However, this contradicts the fact that $G_\omega$ is a Frobenius group. If $G$ is of type TW, then $\Fitt {G_\omega}=1$ by~\cite[Theorem~4.7B~(ii)]{DixMor} (or see also~\cite{me1}). However, this contradicts again the fact that $G_\omega$ is a Frobenius group. Assume that $G$ is a finite primitive group of PA type. Then $G$ is a subgroup of the wreath product $H \mathrm{wr} \Sym(\ell)$ endowed with its natural action on $\Delta^\ell$ with $\ell\geq 2$. Moreover, $H$ is an almost simple primitive group on $\Delta$ and, if we denote by $T$ the socle of $H$, then $G$ has a unique minimal normal subgroup $N$ and $$N=T_1\times\cdots\times T_\ell$$ where $T_i\cong T$ for every $i\in\{1,\ldots,\ell\}$. Furthermore, $\nor G {T_i}$ projects surjectively onto $H$ for every $i\in\{1,\ldots,\ell\}$. Fix $\delta\in \Delta$ and $\omega:=(\delta,\ldots,\delta)\in \Delta^\ell=\Omega$. As $N\unlhd G$ and $N\ne G$, from the structure of $G$, we deduce $N_\omega\unlhd G_\omega$ and $N_\omega\ne G_\omega$, that is, $N_\omega\lhd G_\omega$. Moreover, from the abstract structure of $N$, we obtain $N_\omega\cong T_\delta^\ell$. Let $U$ be the Frobenius kernel of $G_\omega$. From Lemma~\ref{l : 0}, we get that either $N_\omega\le U$ or $U\le N_\omega$. In both cases, $U$ contains a non-identity element of $N_\omega$; so, let $u:=(t_1,\ldots,t_\ell)\in U\cap N_\omega$ with $u\ne 1$. As $u\ne 1$, there exists $i\in \{1,\ldots,\ell\}$ with $t_i\ne 1$. Let $x$ be the element of $N_\omega$ with $t_i$ in coordinate $i$ and $1$ elsewhere. As $u^x=u$ and $G_\omega$ is a Frobenius group, $x$ lies in the Frobenius kernel $U$ of $G_\omega$. Let $j\in\{1,\ldots,\ell\}\setminus\{i\}$. Since $(T_j)_\delta$ centralizes $x\in U$ and since $x$ is contained in the Frobenius group $G_\omega$ having kernel $U$, we deduce $(T_j)_\delta\le U$. Now, $U\lhd G_\omega$ and the action of $G_\omega$ by conjugation on the simple direct factors $\{T_1,\ldots,T_\ell\}$ of $N$ is transitive; hence $(T_j)_\delta\le U$, for every $j\in \{1,\ldots,\ell\}$. This shows that $N_\omega=(T_1)_\delta\times \cdots\times (T_\ell)_\delta\le U$. Suppose that $\nor {G_\omega}{T_1}\le U$. Since $\nor G {T_1}$ projects surjectively onto $H$, the group $\nor {G_\omega}{T_1}$ projects surjectively onto $H_\delta$. Since $U$ is nilpotent, we deduce that $H_\delta$ is nilpotent. As $T_\delta\lhd H_\delta$, there exists $z\in \Zent{H_\delta}\cap T_\delta$ with $z\ne 1$. Set $n:=(z,\ldots,z)\in T_\delta^\ell\le U$. Let $g\in G_\omega\setminus U$. Then we may write $g=\sigma (h_1,\ldots,h_\ell)$, for some $\sigma\in \Sym(\ell)$ and some $h_1,\ldots,h_\ell\in H_\delta$. Observe that, as $g\notin U$, the action of $g$ by conjugation on $U$ fixes no non-identity element. Thus $n^g\ne n$. Now, \begin{eqnarray*} n^g&=&(z,\ldots,z)^{\sigma(h_1,\ldots,h_\ell)}=(z,\ldots,z)^{(h_1,\ldots,h_\ell)}=(z^{h_1},\ldots,z^{h_\ell})=(z,\ldots,z)=n, \end{eqnarray*} which is a contradiction. Therefore, $\nor { G_\omega}{T_1}\nleq U$. Now, let $\pi:\nor {G_\omega}{T_1}\to H_\delta$ be the natural projection. As $G_\omega$ is a Frobenius group with kernel $U$ not containing $\nor {G_\omega}{T_1}$, we get that $H_\delta=\pi(\nor {G_\omega}{T_1})$ is a Frobenius group with kernel $\pi(U)\ge T_\delta$. Summing up, $H$ is an almost simple primitive group on $\Delta$, with socle $T$, with point stabilizer a Frobenius group $H_\delta$ and with Frobenius kernel containing $T_\delta=H_\delta\cap T$. However, this contradicts Lemma~\ref{l : 00}. \end{proof} \begin{hypothesis}\label{h : 1} {\rm In the rest of this section we let $G$ be a finite primitive group on a set $\Omega$ such that, given $\omega\in \Omega$, the point stabilizer $G_\omega$ is a Frobenius group as an abstract group. We assume that $G$ contains a core-free subgroup $X$ with $X$ transitive on $\Omega$ and with $[G:X]=|\Fitt {G_\omega}|$.} \end{hypothesis} \begin{lemma}\label{l : 2} Assume Hypothesis~$\ref{h : 1}$. Then $G$ is a finite primitive group of $\mathrm{AS}$ type and the action of $G$ on the right cosets of $X$ is $2$-transitive. Moreover, %\begin{itemize} %\item every non-trivial normal subgroup of $G$ contains a non-identity element of the Frobenius complement of $G_\omega$.%; %\item either $G_\omega/\Fitt{G_\omega}$ has even order or $[G_\omega :\Fitt{G_\omega}]<|\Fitt {G_\omega}|-1$. %\end{itemize} \end{lemma} \begin{proof} From Lemma \ref{l : 1}, $G$ has type HA or AS. %Let $T$ be the socle of $G$. Suppose first that $T\le X$. This gives $|\Fitt {G_\omega}|=|G:X|\le |G:T|\le |\mathrm{\Aut}(T):T|=|\mathrm{Out}(T)|$, where $\mathrm{Out}(T)$ is the group of outer automorphisms of $T$. In particular, as the size of a Frobenius complement of $G_\omega$ divides $|\Fitt {G_\omega}|-1$. We get $|G_\omega|\le |\mathrm{Out}(T)|(|\mathrm{Out}(T)|-1)$. Suppose that $G$ is a primitive group of HA type and let $V$ be the socle of $G$. Thus $V$ is an elementary abelian $p$-group, for some prime number $p$. Write $|V|=p^\ell$, for some $\ell\in\mathbb{N}\setminus\{0\}$. In particular, $G_\omega$ acts by conjugation irreducibly as a linear group on $V$. Since $\Fitt {G_\omega}$ is nilpotent and $\Fitt{G_\omega}\lhd G_\omega$, $p$ is relatively prime to $|\Fitt{G_\omega}|$. Since, by hypothesis $[G:X]=|\Fitt{G_\omega}|$, we deduce from Sylow's theorems that $V\le X$. However, this contradicts the fact that $X$ is core-free in $G$. Thus $G$ has type AS. As $X$ is transitive on $\Omega$, $G=G_\omega X$ and hence $G$ admits a non-trivial factorization. A finite group $A$ has a non-trivial factorization if, there exist two proper subgroups $B$ and $C$ of $A$ with $A=BC$. The factorization $A=BC$ is said to be maximal if both $B$ and $C$ are maximal subgroups of $A$. Moreover, the factorization is said to be core-free if both $B$ and $C$ are core-free in $A$.) Broadly speaking, finite almost simple groups admitting a maximal core-free factorization are classified by Liebeck, Praeger and Saxl in~\cite{LPS1,LPS2}. Specifically, in~\cite{LPS1}, the authors classify the almost simple groups $G$ admitting a factorization $G=AB$ where $A$ and $B$ are both maximal and core-free in $G$. In~\cite{LPS2}, the authors study and classify a slightly different situation (which suits our current application): they classify the almost simple groups $G$ admitting a factorization $G=AB$ where $A$ and $B$ are core-free and maximal among the core-free subgroups of $G$. In other words, in the factorization $G=AB$, the subgroups $A$ and $B$ are not necessarily maximal in $G$, but all overgroups of $G$ containing properly $A$ (or $B$) must contain the socle of $G$. This more general setting is of interest for our application. By hypothesis $G_\omega$ is maximal in $G$ and $G_\omega$ is core-free in $G$. Moreover, $X$ is core-free in $G$. Among all core-free subgroups of $G$ containing $X$ choose one, say $X'$. Thus $G=G_\omega X'$ is a factorization classified by Liebeck, Praeger and Saxl. Let $T$ be the socle of $G$. A careful analysis of their classification reveals that one of the following holds: \begin{enumerate} \item $T=\Alt(p)$, $\Alt(p)\le G\le \Sym(p)$, $X'=G\cap \Sym(p-1)$ and $G_\omega=\nor G C$ where $C$ is a Sylow $p$-subgroup of $\Alt(p)$ and $p$ is an odd prime with $p\ge 5$; \item $G=T=\Alt(7)$, $X'=\Alt(6)$ and $G_\omega$ has order $21=7\times 3$; \item $G=T=\mathrm{PSL}_2(11)$, $X'=\Alt(5)$ (there are two distinct $G$-conjugacy classes for such $X'$) and $G_\omega$ has order $55=11\times 5$; \item $T=\mathrm{PSL}_n(q)$, $\mathrm{PSL}_n(q)\le G\le \mathrm{P}\Gamma \mathrm{L}_n(q)$, $n$ is prime, $\gcd(n,q-1)=1$, $X'=\nor G B$ where $B$ is a Borel subgroup of $\mathrm{PSL}_n(q)$ and $G_\omega=\nor G C$ where $C$ is a Singer cycle of $\mathrm{PSL}_n(q)$, that is, $C$ is a cyclic subgroup of $\mathrm{PSL}_n(q)$ having order $(q^n-1)/(q-1)$. \end{enumerate} Now, another easy inspection on the classification of Liebeck, Praeger and Saxl yields that $X'=X$ and that the action of $G$ on the right cosets of $X$ in $G$ is $2$-transitive. This inspection is straightforward and we give details only in the case~(1) above. In this case, $\Fitt{G_\omega}$ is cyclic of order $p$ and hence $p=[G:X]\ge [G:X']$. As $X'$ is core-free in $G$ and $G$ has no subgroups having index less then $p$, we get $X'=X$. Now, using~\cite{LPS1,LPS2}, we see that $X=X'$ is either $\Alt(p-1)$ (when $G=\Alt(p)$) or $\Sym(p-1)$ (when $G=\Sym(p)$). Therefore, the action of $G$ on the right cosets of $X$ is $2$-transitive. All other cases are similar. To conclude, observe that for each of the five cases above, the socle $T$ of $G$ contains non-identity elements of the Frobenius complement of $G_\omega$, that is, $T_\omega=T\cap G_\omega$ is not contained in the Fitting subgroup of $G_\omega$ (compared also with Lemma~\ref{l : 00}). \end{proof} \section{Bringing together the various threads of the argument}\label{sec : 4} In this section, we let $F:=N\rtimes H$ be a Frobenius group with kernel $N$ and complement $H$. Let $\mathcal{S}$ be the family of subsets $S$ of $N$ with $F< \Aut(\Cay(N,S))$. We subdivide $\mathcal{S}:=\mathcal{S}_1\cup\mathcal{S}_2\cup\mathcal{S}_3$ in three (not necessarily disjoint) subsets, where \begin{itemize} \item $S\in \mathcal{S}_1$ whenever there exists a non-trivial proper normal subgroup $K$ of $N$ and an automorphism $f\in\Aut(\Cay(N,S))$, with $f\notin N$ and with $f$ fixing setwise every $K$-orbit; \item $S\in\mathcal{S}_2$ whenever $F<\nor {\Aut(\Cay(N,S))} N$; \item $S\in \mathcal{S}_3$ whenever $S\in \mathcal{S}\setminus(\mathcal{S}_1\cup\mathcal{S}_2)$. \end{itemize} Observe that from Theorem \ref{red1}, $|\mathcal{S}_1|\le f_1(|N|,|H|)$ with \begin{align*} f_1(|N|,|K|)&:=2^{(\log_2|N|)^2}\left(\frac{|N|}{2}-1\right)\cdot\\ &\max\left\{2^{1+\frac{|N|-1}{|H|}-\left(\frac{\sqrt{|N|}}{4}-(\log_2|N|)^2\right)},2^{1+\frac{|N|-1}{|H|}-\left(\frac{\sqrt{|N|}-1-|H|}{|H|(1+2|H|)}\log_2(4/3)-2\log_2\sqrt{|N|}+1\right)}\right\}. \end{align*} Moreover, from Corollary \ref{c : 1}, $|\mathcal{S}_2|\le f_2(|N|,|H|)$ with $$f_2(|N|,|H|):=2^{\frac{3}{4}\frac{|N|}{|H|}-\frac{1}{2|H|}+\frac{1}{2}+\sqrt{|N|}\frac{|H|-1}{2|H|}+(\log_2|N|)^2}.$$ Set $$f_3(|N|,|H|):=2^{\frac{3}{2}+\frac{|N|}{|H|}+\frac{1}{2|H|}-F_3(|N|,|H|)+(\log_2|N|)^2}$$ where $$F_3(|N|,|H|)=\frac{1}{4|H|}\min\left\{\left(\frac{2|N|}{|H|}\right)^{2/3}-2|H||N|^{1/2},|N|^{1/2},4|N|^{1/2}-2|H||N|^{1/4}\right\}.$$ Using the results from Section~\ref{sec:primitive}, we prove that $|\mathcal{S}_3|$ is bounded above by $f_3(|N|,|H|)$. To this end, let $S\in \mathcal{S}_3$ and write $\Gamma:=\Cay(N,S)$ and $A:=\Aut(\Gamma)$. Let $B$ be a subgroup of $A$ with $Ff_1(|N|,|H|)+f_2(|N|,|H|)+f_3(|N|,|H|)$, the group $F$ has a DFR. However, when $2^{1+(|N|-1)/|H|}\le f_1(|N|,|H|)+f_2(|N|,|H|)+f_3(|N|,|H|)$, we see that $|N|$ is small compared to $|H|$ and, for any given $|H|$, we may compute the exact values of $|N|$ where this inequality is satisfied. Then, the groups $N$ having these orders can be analyzed separately theoretically or with the aid of a computer. Theoretically this strategy is sound, but in practice, even for relatively small groups $H$, the lower bound on $|N|$ is so large that it seems hopeless and infeasible to study the ``small'' groups $N$ with a computer. } \end{remark} \section{Unlabeled directed Frobenius representations}\label{sec:6} An \emph{unlabeled} (di)graph is simply an equivalence class of (di)graphs under the relation ``being isomorphic to''. We identify a representative with its class. Using this terminology, we have the following unlabeled version of Theorem~\ref{thrm: main1}. \begin{theorem}\label{th:unlabelledmain1} Let $F:=N\rtimes H$ be a finite Frobenius group with kernel $N$ and complement $H$. With $H$ fixed, the ratio of the number of unlabeled $\mathrm{DFR}$ for $F$ over the number of unlabeled Cayley digraphs on $N$ containing $F$ in their automorphism group tends to $1$ as $|N|\to\infty$. \end{theorem} \begin{proof} Let $\Gamma:=\Cay(N,S)$ be a DFR for $F$, that is, $S\subseteq F$ and $F=\Aut(\Cay(N,S))$. We prove that the equivalence class of $\Gamma$ contains at most $2^{(\log_2|N|)^2}$ digraphs, that is, $\{S'\subseteq N\mid \Gamma\cong \Cay(N,S')\}$ has cardinality bounded above by $2^{(\log_2|N|)^2}$. From this, the proof of this theorem immediately follows by repeating verbatim the proof of Theorem~\ref{thrm: main1}. Thus, let $S'\subseteq N$ with $\Gamma\cong \Cay(N,S')$ and let $\varphi:N\to N$ be a digraph isomorphism from $\Gamma$ to $\Cay(N,S')$. Note that $\varphi$ induces a group automorphism from $\Aut(\Gamma)=F$ to $\Aut(\Cay(N,S'))=F$. As $N$ is characteristic in $F$, $\varphi$ induces a group automorphism of $N$; hence $\varphi\in \Aut(N)$ and $S$ and $S'$ are conjugate via an element of $\Aut(N)$. Since $|\Aut(N)|\le 2^{(\log_2|N|)^2}$, the result follows. \end{proof} \begin{thebibliography}{99} \bibitem{babai1}L.~Babai, Finite digraphs with given regular automorphism groups, \textit{Periodica Mathematica Hungarica} \textbf{11} (1980), 257--270. \bibitem{BaGo}L.~Babai, C.~D.~Godsil, On the automorphism groups of almost all Cayley graphs, \textit{European J. Combin.} \textbf{3} (1982), 9--15. %\bibitem{babai3}L.~Babai, C.~D.~Godsil, On the automorphism groups of almost all Cayley graphs, \textit{European J. Combin} \textbf{3} (1982), 9--15. \bibitem{babai2}L.~Babai, W.~Imrich, Tournaments with given regular group, \textit{Aequationes Mathematicae} \textbf{19} (1979), 232--244. \bibitem{11}Y.~Caro, New results on the independence number, \textit{Tech. Report, Tel-Aviv University}, 1979. \bibitem{WT}M.~Conder, T.~Tucker, and M.~Watkins, Graphical Frobenius Representations with even complements, \url{https://www.math.auckland.ac.nz/~dleemans/SCDO2016/SCDO-TALKS/Monday/Tucker.pdf}. \bibitem{DixMor} J.~D. Dixon, B. Mortimer, Permutation Groups. Springer-Verlag, New York, (1996). \bibitem{Dobson2}E.~Dobson, Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power order, \textit{Ars Math. Contemp.} \textbf{3} (2010), 200--213. \bibitem{DSV}E. Dobson, P. Spiga, G. Verret, Cayley graphs on abelian groups, \textit{Combinatorica} \textbf{36} (2016), 371--393. \bibitem{WT1}J.~K.~Doyle, T.~W.~Tucker, and M.~E.~Watkins, Graphical Frobenius Representations, preprint. \bibitem{Godsil}C.~D.~Godsil, GRRs for nonsolvable groups, \textit{Algebraic Methods in Graph Theory,} (Szeged, 1978), 221--239, \textit{Colloq. Math. Soc. J\'{a}nos Bolyai} \textbf{25}, North-Holland, Amsterdam-New York, 1981. \bibitem{GMN}R.~M.~Guralnick, G.~Malle, G.~Navarro, Self-normalazing Sylow subgrous, \textit{Proc. Amer. Math. Soc. }\textbf{132}, 973--979. \bibitem{Hetzel}D.~Hetzel, \"{U}ber regul\"{a}re graphische Darstellung von aufl\"{o}sbaren Gruppen, Technische Universit\"{a}t, Berlin, 1976. \bibitem{Imrich1}W.~Imrich, Graphen mit transitiver Automorphismengruppen, \textit{Monatsh. Math. }\textbf{73} (1969), 341--347. \bibitem{Imrich2}W.~Imrich, Graphs with transitive abelian automorphism group, \textit{Combinat. Theory (Proc. Colloq., Balatonf{\H{u}}red, 1969)}, Budapest, 1970, 651--656. \bibitem{Imrich3}W.~Imrich, On graphs with regular groups, \textit{J. Combinatorial Theory Ser. B} \textbf{19} (1975), 174--180. \bibitem{LZ}C.~H.~Li, H.~Zhang, The finite primitive groups with soluble stabilizers, and the edge-primitive $s$-arc transitive graphs, \textit{Proc. London Math. Soc. }\textbf{103} (2011), 441--472. \bibitem{ONAN} M.~W.~Liebeck, C.~E.~Praeger, J.~Saxl, On the O'Nan-Scott theorem for finite primitive permutation groups, \textit{J. Austral. Math. Soc. Ser. A} \textbf{44} (1988), 389--396. \bibitem{LPS1}M.~W.~Liebeck, C.~E.~Praeger, J.~Saxl, The maximal factorizations of the finite simple groups and their automorphism groups, Memoirs of the American Mathematical Society, Vol. 86, No. 432, American Mathematical Society, Providence, RI, 1990. \bibitem{LPS2}M.~W.~Liebeck, C.~E.~Praeger, J.~Saxl, On factorizations of almost simple groups, \textit{Journal of Algebra} \textbf{185} (1996), 409--419. \bibitem{MSV}J.~Morris, P.~Spiga, G.~Verret, Automorphisms of Cayley graphs on generalised dicyclic groups, \textit{European Journal of Combinatorics} \textbf{43} (2015), 68--81. \bibitem{morrisspiga}J.~Morris, P.~Spiga, Every Finite Non-Solvable Group admits an Oriented Regular Representation, \textit{J. Combin. Theory Ser. B} \textbf{126} (2017), 198--234. \bibitem{morrisspiga2}J.~Morris, P.~Spiga, Classification of finite groups that admit an oriented regular representation, submitted. \bibitem{me1}P.~Spiga, On {$G$}-locally primitive graphs of locally twisted wreath type and a conjecture of {W}eiss, \textit{J. Combin. Theory Ser. A} \textbf{118} (2011), 2257--2260. \bibitem{me2}P. Spiga, Finite groups admitting an oriented regular representation, \textit{J. Combin. Theory Series A} \textbf{153} (2018), 76--97. \bibitem{Spiga}P.~Spiga, Cubic graphical regular representations of finite non-abelian simple groups, \textit{Communications in Algebra}, \textbf{46} (2018) 2440--2450. \bibitem{Spiganow}P.~Spiga, On the existence of graphical Frobenius representations and their asymptotic enumeration: an answer to the GFR conjecture, submitted. \bibitem{40}P.~Tur\'an, An extremal problem in graph theory (hungarian), \textit{Mat. Fiz. Lapok} \textbf{48} (1941), 436--452. \bibitem{41}V.~K.~Wei, A lower bound on the stability number of a simple graph, \textit{Bell Laboratories Technical Memorandum}, 81--11217--9, Murray Hill, NJ, 1981. \bibitem{XF}S.~J.~Xu, X.~G.~Fang, J.~Wang, M.~Xu, On cubic $s$-arc transitive Cayley graphs of finite simple groups, \textit{European J. Combin.} \textbf{26} (2005), 133--143. \end{thebibliography} \end{document}