% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P39}{20(2)}{2013}
\usepackage{amsthm,amsmath,amssymb}
%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{graphicx}
%\parskip 5pt
%%%%%%%%%%%%%%%%%%%%%%%
\def\FF{\mathbb F} \def\ZZ{\mathbb Z}
\def\Aut{{\sf Aut}} \def\Inn{{\sf Inn}}\def\Core{{\sf Core}}
\def\Out{{\sf Out}}
\def\K{{\sf K}}
\def\soc{{\sf soc}}
\def\M{{\rm M}}\def\N{{\rm N}}
\def\Ga{{\it \Gamma}} \def\Si{{\it \Sigma }}
\def\Sig{{\it \Sigma}}
\def\Del{{\it\Delta}}
\def\a{\alpha} \def\b{\beta} \def\d{\delta}\def\g{\gamma} \def\s{\sigma}
\def\t{\tau}  \def\o{\omega}
\def\A{{\rm A}}\def\Sym{{\rm Sym}}
\def\B{{\rm B}}\def\D{{\rm D}} \def\Q{{\rm Q}}
\def\S{{\rm S}} \def\G{{\rm G}}
\def\J{{\rm J}} \def\M{{\rm M}}
\def\PSL{{\rm PSL}}\def\PGL{{\rm PGL}}
\def\GL{{\rm GL}} \def\SL{{\rm SL}}
\def\AGL{{\rm AGL}}
%%%%%%%%%%%%%%%%%%%%%%%
% declare theorem-like environments
\newtheorem{rmk}{Remark}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{que}[thm]{Question}
\newtheorem{pro}[thm]{Proposition}
\newtheorem{con}[thm]{Construction}
\newtheorem{rem}[thm]{Remarks}
\newtheorem{defi}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{core}[thm]{Corollary}
\newtheorem{exa}[thm]{Example}
\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\def\pf{\noindent{\it Proof.} }
\setcounter{section}{0}
\def\qed{\nopagebreak\hfill{\rule{4pt}{7pt}}
\medbreak}

%\setlength{\topmargin}{0cm} \setlength{\oddsidemargin}{0.2cm}
%\setlength{\evensidemargin}{0.2cm} \setlength{\textwidth}{18.8cm}
%\setlength{\textheight}{22.42cm}

\renewcommand{\theequation}{(\arabic{section}.\arabic{equation})}

%\newenvironment{kst}
%{\setlength{\leftmargini}{2.4\parindent}
%\begin{itemize}
%\setlength{\itemsep}{-0.5mm}} {\end{itemize}}

%\oddsidemargin=0.2in \evensidemargin=0.0in \topmargin=-0.4in
%\textwidth=6in \textheight=9in


\title{Affine  primitive groups and Semisymmetric graphs}
\author{ Hua Han \\
\small Center for Combinatorics\\[-0.8ex]
\small LPMC, Nankai University\\[-0.8ex]
\small Tianjin 300071, P. R. China\\
\small\tt hh1204@mail.nankai.edu.cn\\
\and
Zai Ping Lu\thanks{Supported in part by the NSF of China.}\\
\small Center for Combinatorics\\[-0.8ex]
\small LPMC, Nankai University\\[-0.8ex]
\small Tianjin 300071, P. R. China\\
\small\tt lu@nankai.edu.cn\\
}

\date{\dateline{Jul 14, 2012}{May 21, 2013}{May 31, 2013}\\
\small Mathematics Subject Classifications: 05C25, 20B25}

\begin{document}
\maketitle
\begin{abstract}
In this paper, we investigate semisymmetric graphs which arise from affine
primitive permutation groups.
We give a characterization of such graphs, and then construct an infinite
family of semisymmetric graphs which
contains the Gray graph as the third smallest member. Then, as a consequence,
we obtain a factorization
of the complete bipartite graph $\K_{p^{sp^t},p^{sp^t}}$ into connected
semisymmetric graphs, where $p$ is an prime, $1\le t\le s$ with $s\ge2$
while $p=2$.

%\vskip4pt

\bigskip\noindent \textbf{Keywords:} semisymmetric graph; normal quotient; primitive permutation group
\end{abstract}



\section{ Introduction}
All graphs considered in this paper are assumed to be finite and simple with non-empty edge sets.

For a  graph $\Ga$, denote by $V\Ga$,  $E\Ga$
and $\Aut\Ga$ the vertex set,  edge set  and  automorphism group, respectively. A graph $\Ga$ is  said to be {\it vertex-transitive} or
{\it edge-transitive} if $\Aut\Ga$ acts transitively
on $V\Ga$ or  $E\Ga$, respectively. A regular graph is called {\it semisymmetric} if it is edge-transitive but not
vertex-transitive. For a graph $\Ga$, an arc of $\Ga$ is an ordered  pair $(\a,\b)$ of two adjacency vertices.
A graph $\Ga$ is called {\it symmetric} if it has no isolated vertices and $\Aut\Ga$ acts transitively on the set of arcs of $\Ga$.


The class of   semisymmetric graphs was first
studied by Folkman \cite{Folkman}, who possed several open problem.
Afterwards, many authors have done much work on this topic,
see \cite{Bouwer1, Bouwer2, 768,DMar,2pq,
6p2-ssg,bipri-cub,Ivanov,6p2,cubic-2p-3,MP,Monson,2Odd} for references.
In particular, lots of interesting examples of such graphs
were found. For example,  the Folkman graph on $20$ vertices, the
smallest semisymmetric graph,
was constructed by Folkman  \cite{Folkman}; the
%smallest cubic semisymmetric graph, the so-called
Gray graph, a cubic graph of order $54$, was first observed to
be semisymmetric by Bouwer  \cite{Bouwer1}.
%and proved to be the smallest cubic semisymmetric graph by Malni\v{c} et.
%al. \cite{ADPW}.
In 1985, Iofinova and Ivanov \cite{bipri-cub} classified all bi-primitive
cubic semisymmetric graphs and they proved that there are only five
such graphs.

In this paper, we consider the semisymmetric graphs whose automorphism group
contains a subgroup inducing an affine primitive permutation group.
For more information about groups of this kind, see \cite{Lyndon-book,Artzy-book}.
To state
our result, we need to introduce several concepts and some notation.

Let $p$ be a prime and $\FF_p$  the field of order $p$.  Then, for an integer
$l\ge 1$ and an irreducible subgroup
$H$  of the general linear group $\GL(l,p)$, all affine transformations
$\t_{h,v}$ form a primitive subgroup $X$ of $\AGL(l,p)$
(acting on the vectors of $\FF_p^l$), where  $h\in H$, $v\in \FF_p^l$ and
$\t_{h,v}$ is defined as $\FF_p^l\rightarrow\FF_p^l, \, u\mapsto u^h+v$.
The above group is a split extension of a regular normal subgroup
$\{\t_{1,v}\mid v\in \FF_p^l\}$ by the subgroup $H$.
For convenience, for a subspace $V$ of $\FF_p^l$, we set ${\rm
T}(V)=\{\t_{1,v}\mid v\in V\}$
and denote by $N_H(V)$ the subgroup of $H$ fixing $V$ set-wise.
Then $X={\rm T}(\FF_p^l){:}H$,   and $N_H(V)=\N_{H}({\rm T}(V))$, the
normalizer of ${\rm T}(V)$ in $H$.

For a graph $\Ga$ and a subgroup $G\leq \Aut\Ga$, $\Ga$ is said to be
{\it$G$-vertex-transitive}  or {\it$G$-edge-transitive} if $G$ is transitive
on $V\Ga$ or $E\Ga$, respectively.  The graph   $\Ga$ is called
{\it $G$-semisymmetric} graphs if it is regular, $G$-edge-transitive but not
$G$-vertex-transitive.

Let $\Ga$ be a connected $G$-edge-transitive  graph, where $G\le \Aut\Ga$.
%If $\Ga$ is $G$-vertex-transitive, then $\Ga$ is regular.
Assume that $G$ is not transitive on $V\Ga$.
Then $\Ga$ is a bipartite graph
with two parts, say $U$ and $W$, which are  the $G$-orbits on $V\Ga$.
Denote respectively by $G^U$ and $G^W$ the permutation groups induced by $G$
on $U$ and on $W$.
Our main result deals with the  case where one of $G^U$ and $G^W$ is an affine
primitive permutation group.


%It follows that $\Ga$ is semiregular



%A graph is regular if  its vertices have the same valency, and a bipartite
%graph is semirgular if


\begin{thm}\label{main}
Let $X={\rm T}(\FF_p^l){:}H$, where $p$ is a prime, $l\ge 1$ and $H$ is an
irreducible subgroup
of the general linear group $\GL(l,p)$. Then the following two statements
are equivalent.
\begin{enumerate}
\item[(1)] $\FF_p^l$ has an $s$-dimensional subspace $V$ for some integer
$1\le s<l$ such that
$|H:\N_{H}(V)|=p^t$ for some integer $1\le t\le s$.

\item[(2)]
There exists a semisymmetric graph $\Ga$ with bipartition $V\Ga=U\cup W$
with one of $G^U$ and $G^W$  is
permutation isomorphic  to $X$ for some edge-transitive subgroup $G$ of
$\Aut\Ga$.
\end{enumerate}
\end{thm}

%\vskip 10pt

\noindent{\bf Remark}.
Theorem~\ref{main}  suggests the following interesting problem.

{\bf Problem 1}. {\em Characterize  irreducible  subgroups of the general
linear group $\GL(l,p)$ satisfying {\rm Theorem~\ref{main}~(1)}}.

It is well-known that there are no semisymmetric graph of orders $16$, $2p$
and $2p^2$, see \cite{Folkman}.
Thus, for Theorem~\ref{main}~(1), we have $l\ge 3$ and $(p,l)\ne (2,3)$.

%\vskip 20pt

\section{Proof of Theorem~\ref{main}}




Assume that $\Ga$ is a   $G$-edge-transitive but not $G$-vertex-transitive
graph, where $G\le \Aut\Ga$. Then $\Ga$ is a bipartite graph
with two parts, say $U$ and $W$, which are  the $G$-orbits on $V\Ga$. It
follows that $\Ga$ is semiregular, that is,
the vertices in a same bipartition subset have the same valency.
For a given vertex $\a\in V\Ga$,
the stabilizer acts transitively on $\Ga(\a)$. Thus, if $\Ga$ is
vertex-transitive then it must be symmetric.
Take $\b\in \Ga(\a)$. Then each vertex of $\Ga$
can be written as $\a^g$ or $\b^g$ for some $g\in G$. Then, for two arbitrary
vertices $\a^g$ and $\b^h$, they are adjacent in $\Ga$ if and only if $\a$ and
 $\b^{hg^{-1}}$ are adjacent,
i.e., $hg^{-1}\in G_\b G_\a$. Moreover, it is well-known and easily shown that
 $\Ga$ is connected if and only if $\langle G_\a,
 G_\b\rangle=G$.







%For a bipartite graph $\Ga$, with bipartition $V\Ga=U\cup W$. If $\Ga$ is
%$G$-semisymmetric,
% %then for every edge $\{\a,\b\}$, the group
%%$\langle G_\a, G_\b\rangle$ acts transitive on $E\Ga$,
%then $U$ and $W$ are two $G$-orbits. Set $\a\in U,~~\b\in W$, then we may
%write $U$ as the set $[G:G_\a]$, and $G$ acts transitively on $U$ by right
%multiplication, Similarly, $W$ can be denoted by right cosets of $G_\b$ in
%$G$, where $G$ acts transitively on $U$ by right multiplication. If
%$\{\a,\b\}$ is an edge in $\Ga$, it follows that $G_\a\cap G_\b$ is core
%free as $G\leq \Aut\Ga$. And $\Ga$ is connected if and only if $\langle G_\a,
% G_\b\rangle=G$. Since $G_\a~~(G_\b)$ is primitive on
% $\Ga(\a)(resp~~\Ga(\b))$ by right multiplication, the neighbors of
%$\a~~(\b)$ are exactly the images of $\b~~(resp~~\a)$ in
%$G_\a~~(resp~~ G_\b)$. We give adjacency relation of $\Ga$ by
%$$G_\a x\thicksim G_\b y\Longleftrightarrow xy^{-1}\in G_\a G_\b.$$   Hence
% the vertex set and the adjacency  relation of $\Ga$ is exactly denoted by
%the cosets of the point stabilizers.

Let $\Ga$ be a  $G$-semisymmetric graph with two bipartition subsets $U$ and
$W$. Suppose that $G$ has a subgroup $R$
which is regular on both $U$ and $W$. Take an edge $\{\a,\b\}\in E\Ga$.
Then each vertex in $U$ ($W$, resp.) can be written uniquely as $\a^x$
($\b^x$, resp.) for some $x\in R$.
Set $S=\{s\in R\mid \b^s\in \Ga(\a)\}$. Then
$\a^x$ and $\b^y $ are adjacent if and only if $yx^{-1}\in S$. If $R$ is
abelian, then it is
easily shown that $\a^x\mapsto \b^{x^{-1}}, \b^x\mapsto
\a^{x^{-1}},\,\,\forall\,x\in R$ is an automorphism of $\Ga$,
 which leads to the vertex-transitivity of $\Ga$, refer to \cite{2pq,Lu03}.
\begin{lem}\label{bicay}
Let $\Ga$ be a  $G$-semisymmetric graph. Assume  that $G$ has an abelian
subgroup which is regular on both  parts of $\Ga$. Then $\Ga$ is symmetric.
\end{lem}




%Assume further that $G$ contains a abelian subgroup $R$ which is regular on
%$U$ and $W$.


% If $G_\a=1$ for all $\a\in V\Ga$, then $\Ga$ is bi-regular. Let $S$ be a
% subset of $G$, the graph with vertex set $V=\{(g,i)| g\in G, i=0,1\}$ such
%that$$(g,0)\thicksim (h,1)\Longleftrightarrow hg^{-1}\in S.$$ is denoted by
%$\BCay(G, S)$ and call it a {\it bi-Cayley graph}. If $G$ is abelian,
%$\BCay(G, S)$ is vertex-transitive.

Let $\Ga$ be a $G$-semisymmetric graph. Suppose that $G$
has a normal subgroup $N$ which acts
intransitively on at least one of the bipartition subsets of $\Ga$. Then
we define the {\it quotient graph} $\Ga_N$
to have vertices
the $N$-orbits on $V\Ga$, and two $N$-orbits $\Delta$ and $\Delta'$ are
adjacent in $\Ga_N$ if and only
if some $\a\in \Delta$ and some $\b\in \Delta'$   are
adjacent in $\Ga$. It is easy to see that the quotient $\Ga_N$ is a regular
graph if and only if all $N$-orbits have the same length.
%Moreover, if $\Ga_N$ is regular then its valency is a divisor of that of $\Ga$.
%The graph $\Ga$ is called a {\em normal cover} of $\Ga$ (with respect to
%$G$ and $N$) if $\Ga_N$ and $\Ga$ have the same valency,
%which yields that $N$ is the kernel of $G$ acting the $N$-orbits (vertices of
%$\Ga_N$).
%Thus, if $\Ga$ is a normal cover of $\Ga_N$ then the quotient group $G/N$
%can be identified with a subgroup of $\Aut\Ga_N$, and so $\Ga_N$
%is $G/N$-semisymmetric. In particular,  $\Ga$ must be a normal cover of
%$\Ga_N$ if   $\Ga$ is  $G$-locally primitive, refer to \cite{loc-arc-trans}.









%\section{Some graphs associated with primitive permutation groups}

Let $\Ga$ be a finite connected  $G$-semisymmetric graph with $G\le \Aut\Ga$.
Take an edge $\{\a,\b\}\in E\Ga$
and let $U=\a^G$ and $W=\b^G$ be the two $G$-orbits on $V\Ga$.
%Denote  respectively by $G^U$ and $G^W$ the restrictions of $G$ on $U$ and $W$.
Assume that $G$ is unfaithful on $U$, and let $K$ be the kernel of $G$ acting
on $U$. Then $K$ is faithful on $W$, and
each $K$-orbits on $W$ contains at least two vertices. It follows that there
are two distinct vertices in $W$ which have the same
neighborhood in $\Ga$. Thus, as observed in \cite{2pq}, if any two distinct
vertices in $U$ have different neighborhoods in the quotient $\Ga_K$
then $\Ga$ is semisymmetric and  can be reconstructed from $\Ga_K$ as follows.
\begin{con}
{\rm Let $\Sigma$ be a  bipartite  graph with two bipartition subset $U$ and
$\bar W$ such that $m|\bar{W}|=|U|$ for integer $m>1$.
Define a bipartite graph $\Sigma^{1,m}$ with vertex set $U\cup
(\bar{W}{\times}\ZZ_m)$ such that $\a$ and $(\b,i)$ are adjacent
if and only if $\{\a,\b\}\in E\Ga$. For convenience, we set
$\Sigma^{1,1}=\Sigma$.}
\end{con}

For a group $X$, the socle of $X$, denoted by $\soc(X)$, is generated by
all minimal normal subgroups of $X$.
A permutation group is called {\em quasiprimitive} if each of its minimal
normal subgroups is transitive.

\begin{lem}\label{quasiprimitive-case}
Let $\Ga$ be a finite connected  $G$-semisymmetric graph with $G\le \Aut\Ga$.
Take an edge $\{\a,\b\}\in E\Ga$
and set $U=\a^G$ and $W=\b^G$.
% be the two $G$-orbits on $V\Ga$.
%Denote  by $G^U$ and $G^W$ the restrictions of $G$ on $U$.
Assume that $G^U$  is quasiprimitive. Then either $G$ is faithful on both $U$
and $W$, or one of the following statements hold.
\begin{enumerate}
\item[(1)] $\Ga$ is isomorphic to the complete bipartite graph
$\K_{|U|,|U|}$;
\item[(2)] $G$ is faithful on $W$ but not faithful on $U$,  $G^U\cong
G^{\bar W}$,  and $\Ga$
is semisymmetric if further $G^U$ is primitive, where $K$ is the kernel of
 $G$ on $U$ and $\bar W$ is the set of $K$-orbits on $W$.
\end{enumerate}
\end{lem}
\begin{proof} To prove this lemma, we assume next that $G$ is unfaithful
on at least one of $U$ and $W$ and that $\Ga\not\cong \K_{|U|,|U|}$.

Since $G\le \Aut\Ga$, the kernel of $G$ on one bipartition subset must be
faithful on the other one. Then the above assumption implies
that $G$ is faithful on $W$. Thus $G$ is unfaithful on $U$. Let $K$ and
$\bar W$ be as in the lemma. Then $G^U\cong G/K$ and $G$ induces a subgroup
${\bar G}\cong G/K$
of $\Aut\Ga_K$. Suppose that $\bar G$ is unfaithful on $\bar W$. Then it
follows that $\Ga_K\cong \K_{|U|,|{\bar W}|}$, and so
$\Ga\cong \K_{|U|,|U|}$ by noting that $\b^K\subseteq \Ga(\a)$ if $\b\in
 \Ga(\a)$, a contradiction. Thus  $\bar G$ is faithful on $\bar W$,
so $K$ is the kernel of $G$ acting on $\bar{W}$, and
hence $G^U\cong G/K\cong  G^{\bar W}$.

Note that each $K$-orbit on $W$ has size at least $2$, and that two vertices
in a same $K$-orbit have the same neighborhood in $\Ga$.
Assume that $G^U$ is primitive. Then, since $\Ga\not\cong \K_{|U|,|U|}$,  any
two distinct vertices in $U$ have different neighborhood.
Thus there is no $x\in \Aut\Ga$ with $U^x=W$, so $\Ga$ must be semisymmetric. \end{proof}



\begin{core}\label{unfaith}
Let $G$ a finite group which acts faithfully and transitively on both
nonempty sets $U$ and $\bar W$ with $|U|=m|\bar{W}|$ for an integer $m>1$.
For $\a\in U$ and a $G_\a$-orbit $\Theta$ on $\bar{W}$, define a bipartite
graph $\Sigma$ on $U\cup \bar{W}$ such that
$\a^g\in U$ and $\bar{\b}\in \bar{W}$ are adjacent if and only if
$\bar{\b}\in \Theta^g$. If $G^U$ is primitive, then
$\Sigma^{1,m}$ is a semisymmetric graph unless $\Theta=\bar{W}$.
\end{core}
\begin{proof}
Assume that $G^U$ is primitive and  $\Theta\ne \bar{W}$. By
Lemma~\ref{quasiprimitive-case}, it suffices to show
that $\Aut\Sigma^{1,m}$ has an edge-transitive subgroup  which fixes $U$
and induces a permutation group on $U$
permutation isomorphic to $G^U$. Let $Y=G{\times}\ZZ_m$. Define an action
of $Y$ on $V\Sigma^{1,m}$ as follows:
\[(\a^g)^{(x,i)}=\a^{gx},\,\, (\bar{\b},j)^{(x,i)}=(\bar{\b}^x,i+j), \,\,
\forall g,x\in G,\, i,j\in \ZZ_m, \bar{\b}\in \bar{W}.\]
Then, under the above action, $Y$ is a subgroup of $\Aut\Sigma^{1,m}$ as
desired.
\end{proof}

%\vskip 10pt

\noindent {\bf Remark}. A graph is called {\em edge-primitive} if its
automorphism group is primitive on its edge set.
%Let $\Sigma$ be as in Corollary \ref{unfaith} with $G^U$ primitive.
%Assume that $\Sigma$ has girth at least $6$. Define a graph
%$\bar{\Sigma}$ on ${\bar W}$ such that $\bar{\b}_1$ and $\bar{\b}_2$
%are adjacent if and only if they are at distance $2$ in $\Sigma$.
%Then $\bar \Sigma$ is an edge-primitive graph, and $\Theta$ is an orbit
%on $\bar W$ of some edge-stabilizer.
Using Corollary \ref{unfaith}, we can construct examples of semisymmetric
graphs from an edge-primitive graph of  even valency, such as the complete
graph $\K_{2l+1}$, the Perkel graph and etc., by taking $U$, $\bar W$ and
$\Theta$ respectively
the edge set, vertex set and an orbit on $\bar W$ of some edge-stabilizer of
the edge-primitive graph.

%\vskip 10pt
Here we pose the next  interesting problem.

{\bf Problem 2}. {\em Characterize or classify the primitive subgroups of
$\S_n$ which have transitive permutation
representations of degree properly dividing $n$.}

\begin{lem}\label{both-faithful-case}
Let $\Ga$ be a  connected  $G$-semisymmetric graph with $G\le \Aut\Ga$. Take
an edge $\{\a,\b\}\in E\Ga$
and set $U=\a^G$ and $W=\b^G$. Assume that $G$ is faithful on both $U$ and $W$.
%Denote  by $G^U$ and $G^W$ the restrictions of $G$ on $U$.
Assume that $G^U$  is an affine primitive permutation group and
 $\Ga$ is not a complete bipartite graph.
%Set $N=\soc(G)$.
Then either $G$ is primitive on $W$, or
$\Ga$ is semisymmetric.
%, $|N_\b|$ divides $|G_\a|$ and $|G_\a:\N_{G_\a}(N_\b)|$ is a divisor of
%$|N_\b|$ other than $1$.
\end{lem}
\proof Set $N=\soc(G)$. Then $N\cong \ZZ_p^l$ for a prime $p$ and
integer $l\ge 1$.
%$, and $N$ is the unique minimal normal subgroup
%of $G$.
It is easily shown that $G$ is primitive on $W$ if and only if  $N$ is
transitive on $W$.
To finish the proof, in the following, we prove that $\Ga$ is semisymmetric
if  $N$ is intransitive on $W$.

Suppose that $N$ is intransitive on $W$ and $\Ga$ is symmetric. Then $N_\g\ne
1$ for any $\g\in W$. Let $X$ be the set-wise stabilizer of $U$ in $\Aut\Ga$.
Then $G\le X$ and $|\Aut\Ga:X|=2$. Note that $X^U$ is a primitive
permutation group. By Lemma~\ref{quasiprimitive-case}, since $\Ga$ is not a
complete bipartite graph,
we may assume that $X$ is faithful on both $U$ and $W$.
Let $M=\soc(X)$. Take $x\in \Aut\Ga$ with
$\a^x=\b$ and $\b^x=\a$. Then $U^x=W$ and $W^x=U$. Note that $X$ is a
primitive permutation group (on $U$) of degree $p^l$.
Then $M$ is the unique minimal normal subgroup of $X$ by the O'Nan-Scott
Theorem, refer to \cite[Theorem 4.1A]{Dixon-book}.
Thus $M^x=M$, it follows that
$M$ is transitive on both $U$ and $W$.
If $X$ is of affine type then $M=N$ by \cite[Proposition
5.1]{inclusion-problem}, so $N$ is transitive on $U$, a contradiction.
Then, by \cite{abelian-regular} and
\cite[Proposition 5.1]{inclusion-problem}, $N<M$ and $M$ is listed as follows:
\begin{enumerate}
\item[(i)] $M\cong T^l$, where $(p,T)$ is one of $(11, \PSL(2,11))$,
$(11,\M_{11})$, $(23,\M_{23})$ and \\$({q^d-1\over q-1},\PSL(d,q))$; or
\item[(ii)] $M=T_1{\times}\cdots {\times}T_t$ and $N=(N\cap
T_1){\times}\cdots{\times}(N\cap T_t)$, where $T_i=\A_{p^s}$ and
$N\cap T_i\cong \ZZ_p^s$ for $1\le i\le t$, $p^s\ge 5$ and $st=l$.
\end{enumerate}
For (i) and (ii) with $s=1$, the stabilizer $M_\a$ has order coprime to $p$,
and so does for
$M_\a^x=M_\b$, hence $N\cap M_\b=1$, which contradicts that $N_\b\ne 1$. Thus
(ii) occurs and $s\ge 2$, so $p^s>5$.
It is easily shown that $(T_i)_\a\cong \A_{p^s-1}$ and
$M_\a=(T_1)_\a{\times}\cdots{\times}(T_t)_\a$.
Then $M_\b=M_\a^x=((T_1)_\a{\times}\cdots{\times}(T_t)_\a)^x=((T_1\cap
M_\a){\times}\cdots{\times}(T_t\cap
M_\a))^x=(T_1)_\b{\times}\cdots{\times}(T_t)_\b$. It implies that
$\{(T_1)_\a,\cdots,(T_t)_\a\}^x=\{(T_1)_\b,\cdots,(T_t)_\b\}$
as all $(T_i)_\a$ are simple and nonabelian. In particular, $(T_i)_\b\cong
\A_{p^s-1}$,  so
$(T_i)_\a$ and $(T_i)_\b$ are conjugate in $T_i$ for $1\le i\le t$. Thus
$M_\a$ and $M_\b$ are conjugate in $M$.
Since $M$ is transitive on $W$, there is $\g\in W$ with $M_\a=M_\g$. Then
$N_\g=N\cap M_\g=N\cap M_\a=1$ as $N$ is regular on
$U$,   again a contradiction. This completes the proof.
\qed

\noindent {\bf Remark} It is well-known that
there are no symmetric graphs of order $2p$ and $2p^2$. Thus, for
Lemma~\ref{both-faithful-case}, if $N$ is intransitive on $W$ then $N\cong
\ZZ_p^l$ for
$l\ge 3$, which also follows from checking the irreducible subgroups of $\GL(2,p)$.

%\vskip 10pt

\noindent{\bf Proof of Theorem~\ref{main}}.
Let $\Ga$ be a semisymmetric graph with bipartition $V\Ga=U\cup W$ satisfying
Theorem~\ref{main}~(2). Then $\Ga$ must be connected.
Without loss of generality, we assume that $G^U$ is permutation isomorphic to
$X$. By Lemma~\ref{quasiprimitive-case},
$G$ is faithful on $W$. Let $K$ be the kernel of $G$ acting on $U$ and
$\bar W$ be the set of $K$-orbits on $W$,
while $K=1$ and $\bar{W}=W$ if $G$ is faithful on $U$. Then, by
Lemmas~\ref{quasiprimitive-case} and \ref{both-faithful-case},
$\Ga_K$ is edge-transitive but not vertex-transitive. Let $\bar G$ be
the subgroup of $\Aut\Ga_K$ induced by $G$. Then ${\bar G}\cong G/K$,
and ${\bar G}^U$ is permutation isomorphic to $X$.

Set $N=\soc({\bar G})$. Suppose that $N$ is transitive on $\bar W$. Then,
since $N$ is faithful on $\bar W$, we have
$|\bar{W}|=|N|=|U|$. Thus $K=1$ and $\Ga=\Ga_K$, $\Ga$ is symmetric by
Lemma~\ref{bicay}, a contradiction. Then
$N$ is intransitive on $\bar W$.  Take an edge $\{\a,\bar{\b}\}$ of $\Ga_K$
with $\a\in U$ and $\bar{\b}\in \bar{W}$.
Then each $N$-orbit on $\bar W$ has size $|N{:}N_{\bar\b}|\ne 1$, and $N$ has
exactly $|\bar{W}|\over |N:N_{\bar\b}|$ orbits on $\bar W$.
Set $|N_{\bar\b}|=p^s$ and ${|\bar{W}|\over |N:N_{\bar\b}|}=p^r$. Then $1\le
r\le s<l$.
Since $\bar G$ is transitive on $\bar W$, we know that ${\bar G}_\a$ is
transitive on the set of $N$-orbits.
Let $B$ be an $N$-orbit containing $\bar\b$. Then $|{\bar G}_\a:({\bar
G}_\a)_B|=p^r$.
Since $\bar{G}_\a$ is maximal in $\bar G$, we have
$\bar{G}_\a\not\le \N_{\bar G}(N_{\bar{\b}})$. So $|{\bar G}_\a:\N_{{\bar
G}_\a}(N_{\bar \b})|>1$.
Consider the set-wise stabilizer $({\bar G}_\a)_B$. For
$g\in ({\bar G}_\a)_B$, noting that $N_{\bar \b}$ is the kernel of $N$
acting on $B$, we have ${\bar \b}^{gx}=\bar{\b}^g$ for $x\in N_{\bar \b}$,
so $gxg^{-1}\in N\cap {\bar G}_{\bar \b}=N_{\bar \b}$. Thus
$({\bar G}_\a)_B\le \N_{{\bar G}_\a}(N_{\bar \b})$.
Set $|{\bar G}_\a:\N_{{\bar G}_\a}(N_{\bar \b})|=p^t$. Then $t\ge 1$, and
 $p^t$ divides $|{\bar G}_\a:({\bar G}_\a)_B|=p^r$, so $t\le r\le s$.
Noting that ${\bar G}^U$ is permutation isomorphic to $X$, (1) of
Theorem~\ref{main} follows.

Now we assume that Theorem~\ref{main} (1) holds. To show (2), it suffices to
construct a suitable semisymmetric graph.
Set $R={\rm T}(V)\N_H(V)$. Let $\bar W$ be the set of right cosets of $R$ in
$X$, and let $U$ be the set of vectors in $\FF_p^l$.
Then $|\bar{W}|=p^{l-s+t}$. Extend $X$ to a permutation group  on
$U\cup {\bar W}$ such that $X^U=X$ and $X$ acts on $\bar W$ by
the right multiplication on the right cosets of $R$ in $X$. It is easily
shown that $X$ is faithful on both $U$ and $\bar W$.
Let $\Theta=\{Rh\mid h\in H\}$. Then $|\Theta|={|V||H|\over
|R|}=|H:\N_H(V)|=p^t<|\bar{W}|$.
Define a bipartite graph $\Sigma$ on $U\cup \bar{W}$ such that
$u\in U$ and $\bar{\b}\in \bar{W}$ are adjacent if and only if $\bar{\b}\in
\Theta^{\t_{1,u}}$. Then $\Sigma$ is $X$-edge-transitive.
Let $m=p^{s-t}$. If $m=1$ then, by Lemma~\ref{both-faithful-case}, $\Sigma$
is a semisymmetric graph as desired. If
$m>1$ then, by Corollary~\ref{unfaith}, $\Sigma^{1,m}$ is a
semisymmetric graph as desired. This completes the proof.
%, and the lemma follows.
\qed


%\noindent {\bf Remark}.

\section{Some examples}
Let $X={\rm T}(\FF_p^l){:}H$ be a primitive permutation group satisfying
Theorem~\ref{main}~(1). Then, up to isomorphism, each graph satisfying
Theorem~\ref{main}~(2) can be constructed from an $X$-edge-transitive
graph which is  not a complete bipartite graph and has one bipartition subset
coinciding with the underlaying set of $\FF_p^l$. Let $\Sigma$ be such an
$X$-edge-transitive graph with
two bipartition subsets $U=\FF_p^l$ and $W$. Then, for each $\b\in W$, the
stabilizer $X_\b$
normalizes $({\rm T}(\FF_p^l))_\b={\rm T}(V)$, where $V$ is an
$s$-dimensional subspace of $U$ and  $X_\b\cap {\rm T}(\FF_p^l)={\rm T}(V)$.
Thus $X_\b\le \N_X({\rm T}(V))={\rm T}(\FF_p^l)\N_H(V)$. Assume that ${\rm
T}(\FF_p^l)$ has $p^r$ orbits on $W$,
and set $|H:\N_H(V)|=p^t$. Then $1\le t\le r\le s<l$, and
$|X_\b|=p^{s-r}|H|$. We next consider one extreme case.

Assume that $X_\b={\rm T}(V){:}\N_H(V)$. Then $r=t$, and $W$ may be
identified with $\cup_{h\in H}\{u+V^h\mid u\in \FF_p^l\}$ with the
action of $X$ on $W$ as follows:
\[(u+V^h)^{\t_{1,u'}h'}=(u+u')^{h'}+V^{hh'}\,\, \forall \,u,u'\in \FF_p^l,\,
h,h'\in H.\]
For each $u\in U=\FF_p^l$, set $\Theta(u)=\{u^h+V^h\mid h\in H\}$. Then
$\{\Theta(u)\mid u\in \FF_p^l\}$
is the set of $H$-orbits on $W$. Moreover, $|\Theta(0)|=p^t<|W|=p^{l-s+t}$,
and so $|\Theta(u)|<|W|$
for each $u\in U$. Thus $\Sigma$ is isomorphic to one of the graphs
constructed as follows.

\begin{con}\label{con}
{\rm Let $p$, $l$, $H$ and $V$ be as in Theorem~\ref{main}~(1). Let
$U=\FF_p^l$ and $W=\cup_{h\in H}\{u+V^h\mid u\in \FF_p^l\}$.
For each $u_0\in U$, define a bipartite graph $\Ga(p,l,s, t;H,u_0)$ on
$U\cup W$ such that
$u\in U$ and $u'+V^{h'}\in W$ are adjacent if and only if
\[u'+V^{h'}=u+u_0^h+V^h \mbox{ for some } h\in H,\]\mbox{ i.e.},\[
u_0+(u-u')^{h^{-1}}\in V \mbox{ and }
h'h^{-1}\in N_H(V) \mbox{ for some } h\in H.\]}
\end{con}

The next result follows from Lemmas~\ref{quasiprimitive-case} and
\ref{both-faithful-case}, Corollary
\ref{unfaith} and the above argument.
\begin{core}
If there is a graph $\Sigma=\Ga(p,l,s, t;H,u_0)$   as in {\rm
Construction~\ref{con}}, then $\Sigma^{1,p^{s-t}}$ is semisymmetric.
\end{core}

Now we construct an infinite family of semisymmetric graphs.

\begin{exa}\label{exam1}
{\rm Let $p$ be a prime, and let $s$ and $t$ be two integers with $1\le t\le s$
%, and let $p$ be a prime.
such that $s\ge 2$ if further $p=2$.
Let $l=sp^t$. Write $\FF_p^l$ in a direct sum
\[\FF_p^l=\bigoplus_{i=1}^{p^t} U_i\]
of $s$-dimensional subspaces.
Without loss of generality, for each $i$, we take
$\{e_{ij}\mid 1\le j\le s\}$ as a basis of $U$,
where $e_{ij}$ is the column vector with the $((i-1)s+j)$-th entry equal
to 1 and the other entries equal to zero.

Let $H$ be the subgroup of $\GL(l,p)$ fixes the above decomposition. Then
$H\cong \GL(s,p)\wr \S_{p^t}$.
Let $V=U_1$ and $\Sigma=\Ga(p,l,s, t;H,u)$. Set
\[G(p,s,t;u)=\Sigma^{1,m}, \mbox{ where } m=p^{s-t}\]
with $\Sigma^{1,m}=1$ while $m=1$.
Then we get a family
\[\mathcal{G}=\{G(p,s,t;u)\mid 1\le t\le s, p \mbox{ is a prime}, (p,s)\ne
(2,1), u\in \FF_p^{sp^t}\}\]
of semisymmetric graphs, and the following statements hold:
\begin{enumerate}
\item[(i)] $G(p,s,t;0)$ has valency $p^s=p^tp^{s-t}$;

\item[(ii)] $G(p,s,t;u)=G(p,s,t;u')$ if $u-u'\in U_i$ for some $1\le i\le p^t$;
\item[(iii)] $G(p,s,t;e_{i1})=G(p,s,t;e_{i'1})$ for $i,i'\ge 2$;
\item[(iv)] $G(p,s,t;e_{21})$ has valency $p^s(p^s-1)(p^t-1)$;
\item[(v)] $G(p,s,t;\sum_{a=1}^ku_{i_a})=G(p,s,t;\sum_{a=1}^ke_{{i_a}1})$ for $2\le i_1<i_2<\cdots i_k\le p^t$ and $u_i\in U_i\setminus\{0\}$;
\item[(vi)] $G(p,s,t;\sum_{i=2}^ke_{i1})$ has valency $p^s(p^{s}-1)^{k-1}(^{p^t-1}_{k-1})$, where $ 2\le k\le p^t$.
\end{enumerate}

Therefore the complete graph $K_{p^{sp^t},p^{sp^t}}$ can be factorized into
$p^t$ connected semisymmetric graphs.
In particular, $K_{27,27}$ is the edge-disjoint union of three semisymmetric
graphs of valency $3$, $12$ and $12$, say,
$G(3,1,1;0)$, $G(3,1,1;e_{21})$ and $G(3,1,1;e_{21}+e_{31})$.

By \cite{768}, there is a unique cubic semisymmetric graph of order $54$.
Thus $G(3,1,1;0)$ is in fact the Gray graph. The smallest members of
$\mathcal{G}$ have order $32$, which
are $G(2,2,1;0)$ and $G(2,2,1;e_{21})$ and have valency $4$ and $12$,
respectively.}
\end{exa}

%\vskip 10pt

%\noindent {\bf Remark}.
It is easily shown that, for $s\ge 2$, we can get the same graphs as in
Example~\ref{exam1} if replace $H$ by $H\cap \SL(l,p)$.
This is also true for $s=1$ unless $p=3$.

\begin{exa}\label{exam2}
{\rm Let  $p$ be an odd prime. Write $\FF_p^p$ in a direct sum
$\FF_p^p=\bigoplus_{i=1}^{p} U_i$ of $1$-dimensional subspaces.
Assume that $e_i\in U_i$ for each $i$,
where $e_i$ is the column vector with the $i$-th entry equal to 1 and the
other entries equal to zero.
Let $H$ be the subgroup of $\SL(p,p)$ fixes the above decomposition. Then $H\cong \ZZ_{p-1}^{p-1}{:}\A_{p}$.
Let $V=U_1$ and \[S(p,p;u)=\Ga(p,p,1, 1;H,u).\]
Then each $S(p,p;u)$
%we get a family $\mathcal{S}=\{S(p,p;u)\mid   p \mbox{ is an odd prime},
%u\in \FF_p^p\}$ of
is semisymmetric graph, and the following statements hold:
\begin{enumerate}
\item[(i)] $S(p,p;0)=G(p,1,1;0)$ has valency $p$;

%\item[(ii)] $G(p,s,t;u)=G(p,s,t;u')$ if $u-u'\in U_i$ for some $1\le i\le p^t$;
\item[(ii)] $S(p,p;e_i)=G(p,1,1;e_i)$  has valency $p(p-1)^2$,
for $p\ge 5$ and $2\le i\le p$;
\item[(iii)] $S(3,3;e_2)$ and  $S(3,3;e_3)$ have valency $6$, and $G(3,1,1,e_2)$
is the edge-disjoint union of these two graphs;
%\item[(iv)] $G(p,s,t;e_{21})$ has valency $p^s(p^s-1)(p^t-1)$;
%\item[(v)] $G(p,s,t;\sum_{a=1}^ku_{i_a})=G(p,s,t;\sum_{a=1}^ke_{{i_a}1})$
%for $2\le i_1<i_2<\cdots i_k\le p^t$ and $u_i\in U_i\setminus\{0\}$;
\item[(iv)] $S(p,p;\sum_{i=2}^ke_i)=G(p,1,1;\sum_{i=2}^ke_i)$ has valency
$p(p-1)^{k-1}(^{p-1}_{k-1})$ for $k\ge 3$.
%\item[(v)] $S(p,p;\sum_{i=2}^ke_i)$
% has valency $p^s(p^{s}-1)^{k-1}(^{p^t-1}_{k-1})$, where $ 2\le k\le p^t$.
\end{enumerate}
}
\end{exa}


\begin{thebibliography}{99}
\bibitem{Bouwer1} I.~Z. Bouwer.
\newblock An edge but not vertex transitive cubic graphs.
\newblock {\em Canad Math. Bull.}, 11:533--535, 1968.

\bibitem{Bouwer2} I.~Z. Bouwer.
\newblock On edge but not vertex transitive graphs.
\newblock {\em J. Combin. Theory Ser. B}, 12:32--40, 1972.


\bibitem{768} M.~Conder, A.~Malni\v{c}, D.~Maru\v{s}i\v{c} and P.~Poto\v{c}nik.
\newblock A census of semisymmetric cubic graphs on up to $768$ vertices.
\newblock {\em J. Algebr. Comb.}, 23:255--294, 2006.


\bibitem{Dixon-book}J.~D. Dixon and B.~Mortimer.
\newblock {\em Permutation Groups}.
\newblock Springer-Verlag  New  York  Berlin  Heidelberg,  1996.

\bibitem{Lyndon-book}R.~Lyndon.
\newblock{\em Groups and Geometry}.
\newblock Cambridge University Press, Cambridge, 1985.

\bibitem{Artzy-book}R.~Artzy.
\newblock{\em Linear Geometry}.
\newblock Addison--Wesley, 1965.

\bibitem{DMar} S.~F. Du and D.~Maru\v{s}i\v{c}.
\newblock Biprimitive Graphs of Smallest Order.
\newblock {\em J  Algebr. Comb.}, 9:151--156, 1999.

\bibitem{2pq} S.~F. Du and  M.~Y. Xu.
\newblock A classification of semisymmetric graphs of order $2pq$.
\newblock {\em Comm. Algebra}, 28(6):2685--2714, 2000.


\bibitem{Folkman} J.~Folkman.
\newblock Regular line-symmetric graphs.
\newblock {\em J. Combin.Theory Ser. B}, 3:215--232, 1967.

\bibitem{6p2-ssg} H.~Han and  Z.~P. Lu.
\newblock Semisymmetric graphs of order $6p^2$ and prime valency.
\newblock {\em Sci. China Math.}, 55:2579--2592, 2012.
%doi:10.1007/s11425-012-4424-9, 2012.

\bibitem{bipri-cub}
M.~E. Iofinova and A.~A. Ivanov. \newblock Biprimitive cubic graphs
(Russian), in: \newblock{\em Investigation in Algebraic
Theory of Combinatorial Objects, Proc. of the Seminar, Institute for System
Studies, Moscow}, pp.124--134, 1985.

\bibitem{Ivanov} A.~V. Ivanov.
\newblock On edge but not vertex transitive regular graphs.
\newblock{\em Ann.  Discrete Math.}, 34:273--286, 1987.

\bibitem{abelian-regular} C.~H. Li.
\newblock The finite primitive permutation groups containing
an abelian regular subgroup,
\newblock {\em Proc. London Math. Soc.},  87(3):725--747, 2003.

\bibitem{Lu03}  Z.~P. Lu.
\newblock On the automorphism groups of bi-Cayley graphs.
\newblock {\em  Beijing Daxue Xuebao}  39:1--5, 2003.

\bibitem{6p2} Z.~P. Lu,  C.~Q. Wang and  M.~Y. Xu.
\newblock On Semisymmetric Cubic Graphs of Order $6p^2$.
\newblock {\em Sci.China Ser.A }, 47:1--17, 2004.

\bibitem{cubic-2p-3} A.~Malni\v{c}, D.~Maru\v{s}i\v{c} and C.~Q. Wang.
\newblock Cubic edge-transitive graphs of order $2p^3$.
\newblock {\em Discrete Math.}, 274:187--198, 2004.

\bibitem{MP} D.~Maru\v{s}i\v{c} and P.~Poto\v{c}nik.
\newblock Semisymmetry of generalized Folkman graphs.
\newblock {\em European J.  Combin.}, 22:333--349, 2001.

\bibitem{Monson} B.~Monson, T.~Pisanski, E.~Schulte and A.~I. Weiss.
\newblock Semisymmetric graphs from polytopes.
\newblock {\em J. Combin. Theory Ser. A}, 114:421--435, 2007.

\bibitem{2Odd} C.~W. Parker.
\newblock Semisymmetric cubic graphs of twice odd order.
\newblock {\em European J.  Combin.}, 28:572--591, 2007.

\bibitem{inclusion-problem} C.~E. Praeger.
\newblock The inclusion problem for finite primitive permutation groups.
\newblock {\em Proc. London Math. Soc.}, 60(3):68--88, 1990.

\end{thebibliography}
\end{document}



\bibitem{atlas}
J.H. Conway, R.T. Curtis, S.P. Noton, R.A. Parker and R.A. Wilson,
{\em Atlas of Finite Groups}, Clarendon Press, Oxford, 1985.


\bibitem{sympq}
C.E. Praeger, M.Y. Xu, Symmetric graphs of order a product of two distinct primes,{\it J.
Combin. Theory Ser. B}, {\bf 59} (1993) 245--266.
\bibitem{Liebeck} Peter Kleidman, Martin Liebeck, \emph{The subgroup structure of the finite
classical groups},
Cambridge University Press, 1990.

\bibitem{WX}
R.J. Wang and M.Y. Xu, A classification of symmetric graphs of order $3p$,
{\em J. Combin. Theory Ser. B} {\bf 58} (1993), 197--216.
\bibitem{cover-K_{3,3}}
C.Q. Wang and T.S. Chen, Cubic semisymmetric graphs as regular covers of $K_{3,3}$,
{\it Acta Math.Sincia, English Series Mar.} {\bf 24} (2008), 405--416.
