% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P56}{20(1)}{2013} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % 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}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\ld}{,\ldots,} \newcommand{\nni}{\not\in } \newcommand{\se}{ \subseteq } \newcommand{\lan}{ \langle } \newcommand{\ran}{ \rangle } \newcommand{\CC}{\mathop{\bf C}\nolimits} \newcommand{\FF}{\mathop{\bf F}\nolimits} \newcommand{\GG}{\mathop{\bf G}\nolimits} \newcommand{\Hom}{\mathop{\rm Hom}\nolimits} \newcommand{\NN}{\mathop{\bf N}\nolimits} \newcommand{\QQ}{\mathop{\bf Q}\nolimits} \newcommand{\RR}{\mathop{\bf R}\nolimits} %\newcommand{\ZZ}{\mathop{\bf Z}\nolimits} \newcommand{\rank}{\mathop{\rm rank}\nolimits} \def\ZZ{{\mathbb Z}} \def\calB{{\mathcal B}} \def\calC{{\mathcal C}} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\ga}{\gamma} \newcommand{\de}{\delta} \newcommand{\ep}{\varepsilon} \newcommand{\eps}{{\varepsilon}} \newcommand{\lam}{\lambda } \newcommand{\dij}{_{ij}} \newcommand{\dkl}{_{kl}} \newcommand{\dst}{_{st}} \newcommand{\dnn}{_{nn}} \newcommand{\dmn}{_{mn}} \newcommand{\dmm}{_{mm}} \newcommand{\up}{^{-1}} \newcommand{\iin}{$(i=1,\ldots,n)$} \newcommand{\sig}{\sigma } \newcommand{\Om}{\Omega } \def\l{\langle} \def\r{\rangle} %%%% Roman Math %%%%% \def\L{{\rm L}} \def\U{{\rm U}} \def\PSL{{\rm PSL}}%\nolimits} \def\SL{{\rm SL}}%\nolimits} \def\SO{{\rm SO}}%\nolimits} \def\PSO{{\rm PSO}}%\nolimits} \def\Spin{{\rm Spin}}%\nolimits} \def\PSU{{\rm PSU}}%\nolimits} \def\SU{{\rm SU}}%\nolimits} \def\PSp{{\rm PSp}}%\nolimits} \def\PGU{{\rm PGU}}%\nolimits} \def\GU{{\rm GU}}%\nolimits} \def\GL{{\rm GL}}%\nolimits} \def\PGL{{\rm PGL}}%\nolimits} \def\Cl{{\rm Cl}}%\nolimits} \def\Sp{{\rm Sp}}%\nolimits} \def\A{{\rm A}}%\nolimits} \def\FGL{{\rm FGL}}%\nolimits} \def\FSL{{\rm FSL}}%\nolimits} \def\J{{\rm J}} \def\M{{\rm M}} \def\Suz{{\rm Suz}} \def\E{{\rm E}} \def\F{{\rm F}} \def\G{{\rm G}} \def\Sz{{\rm Sz}} \def\AGL{{\rm AGL}} \def\AGammaL{{\rm A\Gamma L}} \def\Ru{{\rm Ru}} \def\POmega{{\rm P\Omega}} \def\PSigmaL{{\rm P\Sigma L}} \def\PGammaL{{\rm P\Gamma L}} \def\Sz{{\rm Sz}} \def\Ree{{\rm Ree}} \def\K{{\bf K}} \def\Z{{\bf Z}} %\def\A{{\rm A}}%\nolimits} \def\B{{\rm B}}%\nolimits} \def\C{{\rm C}}%\nolimits} \def\D{{\rm D}}%\nolimits} \def\E{{\rm E}}%\nolimits} \def\F{{\rm F}}%\nolimits} \def\G{{\rm G}}%\nolimits} %\def\O{{\rm O}}%\nolimits} \def\U{{\rm U}}%\nolimits} \def\Sym{{\rm Sym}} \def\Alt{{\rm Alt}} \def\Aut{{\rm Aut}} \def\Out{{\rm Out}} \def\CSym{{\rm CSym}} \def\Char{{\rm char}} \def\Inn{{\rm Inn}} \def\Cay{{\sf Cay}} \def\BCay{{\sf BCay}} \def\Aut{{\sf Aut}} \def\Cos{{\sf Cos}} \def\char{{\sf \,char\,}} \def\soc{{\sf soc}} \def\FIF{\mathrm{FIF}} \def\KG{{\bf KG}} %------------------------------------ \def\Ga{{\it \Gamma}} \def\Sig{{\it \Sigma}} \def\Del{{\it \Delta}} \def\Ome{{\it \Omega}} \def\N{{\bf N}} \def\C{{\bf C}} \def\S{{\rm S}} \def\A{{\rm A}} \def\rmO{{\rm O}} \def\rmQ{{\rm Q}} \def\O{{\rm O}} \def\J{{\bf J}} \def\K{{\bf K}} \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\s{\sigma} \def\t{\tau} \def\ov{\overline} \def\mod{{\sf mod\ }} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf A family of half-transitive graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Jing Chen\thanks{This work was partially supported by an ARC Discovery Project Grant, NNSF of China(No. 11171292, 11271208) and Hunan First Normal University(No. XYS12N12).}\\ \small Department of Mathematics\\[-0.8ex] \small Hunan First Normal University\\[-0.8ex] \small Changsha, P. R. China\\ \small\tt chenjing827@126.com\\ \and Cai Heng Li\\ \small School of Mathematics and Statistics\\[-0.8ex] \small Yunnan University\\[-0.8ex] \small Kunming, P. R. China\\ \small\tt cai.heng.li@uwa.edu.au\\ \and \'Akos Seress\\ \small School of Mathematics and Statistics \\[-0.8ex] \small The Ohio State University\\[-0.8ex] \small The University of Western Australia\\[-0.8ex] \small Crawley, WA 6009, Australia } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Dec 15, 2011}{Mar 1, 2013}{Mar 8, 2013}\\ \small Mathematics Subject Classifications: 05C25, 20B25} \begin{document} \maketitle \begin{abstract} We construct an infinite family of half-transitive graphs, which contains infinitely many Cayley graphs, and infinitely many non-Cayley graphs. % keywords are optional \bigskip\noindent \textbf{Keywords:} half-transitive graphs; quotient graphs; automorphism groups. \end{abstract} \section{Introduction} Let $\Ga=(V,E)$ be a graph with vertex set $V$ and edge set $E$. A permutation of $V$ which preserves the adjacency of $\Ga$ is an automorphism of the graph, and all automorphisms form the automorphism group $\Aut\Ga$. If a subgroup $G\le\Aut\Ga$ is transitive on $V$ or $E$, then $\Ga$ is called {\it $G$-vertex-transitive} or {\it $G$-edge-transitive}, respectively. An ordered pair of adjacent vertices is called an {\it arc}, and $\Ga$ is called {\it arc-transitive} if $\Aut\Ga$ is transitive on the set of arcs. An arc-transitive graph is vertex-transitive and edge-transitive, but the converse statement is not true. A graph which is vertex-transitive and edge-transitive but not arc-transitive is called {\it half-transitive}. The study of half-transitive graphs was initiated with a question of Tutte \cite[p.\,60]{Tutte} regarding their existence, and he proved that a vertex-transitive and edge-transitive graph with odd valency must be arc-transitive. Bouwer \cite{Bouwer} in 1970 constructed the first family of half-transitive graphs. Since then, constructing and characterizing half-transitive graphs has been an active topic in algebraic graph theory, refer to \cite{AMN,A-Xu,Li-Sim,MP,Sajna,Xu} and a survey \cite{Marusic} for the work during 1990's, and \cite{M-Sparl,Sajna,Song,Sparl-08,Sparl} for more recent work. In this paper, we present an infinite family of half-transitive graphs. These graphs were originated from {\it Johnson graphs} $\J(n,i)$ where $i=1$, 2 or 3, the vertex set of which consists of the $i$-element subsets of an $n$-element set such that two vertices are adjacent when they meet in $(i-1)$-elements. It is known that the automorphism group of $\J(n,i)$ is $\S_{n}$, see \cite{Jones} or \cite[Theorem 1]{mark-Johnson}. As usual, we denote by $[n]$ the set $\{1,2,3,\ldots,n\}$. Let \[V_n=\{\{\{i,j\},k\}\mid i,j,k\in [n]\}.\] For convenience, we simply write the vertex $\{\{i,j\},k\}$ as $(ij,k)$. Then $(ij,k)=(ji,k)$, and a 3-subset $\{i,j,k\}$ corresponds to exactly three vertices $(ij,k)$, $(ik,j)$ and $(jk,i)$. Thus, the cardinality is \[|V_n|=3{n\choose3}=n(n-1)(n-2)/2.\] \begin{definition}\label{def-Gamma} {\rm For an integer $n>3$, let $\Ga_n$ be the graph with vertex set $V_n$ such that two vertices $(ij,k)$ and $(i'j',k')\in V_n$ are adjacent if and only if \[\mbox{$\{i,j\}=\{i',k'\}$ or $\{j',k'\}$}\]}% and $\{i,j,k\}\neq\{i',j',k'\}$. \end{definition} The graph $\Ga_n$ is regular and has valency $4(n-3)$. For example, the vertex $(12,3)$ has neighborhood \[\{(1i,2),(2i,1),(13,i),(23,i) \mid i>3\},\] which has size $4(n-3)$. Let $\Ga=(V,E)$ be a graph, and let $\calB$ be a partition of the vertex set $V$. Then the {\it quotient graph} $\Ga_\calB$ induced on $\calB$ is the graph with vertex set $\calB$ such that $B,B'$ are adjacent if and only if there is an edge which lies between $B$ and $B'$. In this case, $\Ga$ is also said to be {\it homomorphic} to $\Ga_\calB$. A graph $\Ga=(V,E)$ is called a {\it Cayley graph} if there is a group $R$ and a self-inversed subset $S\subset R$ such that $V=R$ and $u,v\in S$ are adjacent if and only if $vu^{-1}\in S$. Cayley graphs are vertex-transitive, but a vertex-transitive graph is not necessarily a Cayley graph. For example, the Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. The family of graphs $\Ga_n$ contains infinitely many non-Cayley graphs. \begin{theorem}\label{main-thm} Let $\Ga_n$ be a graph defined above. Then the following statements hold: \begin{itemize} \item[(i)] $\Ga_n$ is of order ${n(n-1)(n-2)\over2}$, valency $4(n-3)$, girth $3$, and diameter $3$; \item[(ii)] $\Ga_n$ is homomorphic to $\K_n$, $\J(n,2)$ and $\J(n,3)$; \item[(iii)] $\Ga_4$ and $\Ga_5$ are arc-transitive, and for $n\ge6$, $\Aut\Ga_n=\Sym([n])$, and $\Ga_n$ is half-transitive; \item[(iv)] $\Ga_n$ is a Cayley graph if and only if $n=8$, or $n=q+1$ with $q$ a prime-power, and $q\equiv 3$ $(\mod 4)$. \end{itemize} \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Edge-transitivity} Let $\s\in\Sym([n])$. For convenience, we simply denote $V_n$ by $V$, and denote $\Ga_n$ by $\Ga$. Then $\s$ induces a permutation on the vertex set $V$. Since $G=\Sym([n])$ is 3-transitive on $[n]$, $G$ is transitive on $V$. Take an edge $\{(i_1j_1,k_1), (i_2j_2,k_2)\}$ of $\Ga$. Then $\{i_1,j_1\}=\{i_2,k_2\}$ or $\{j_2,k_2\}$, and hence $\{i_1^\s,j_1^\s\}=\{i_2^\s,k_2^\s\}$ or $\{j_2^\s,k_2^\s\}$. Thus, $(i_1^\s j_1^\s,k_1^\s)$ and $(i_2^\s j_2^\s,k_2^\s)$ are adjacent, that is, $\s$ maps edges to edges. Similarly, $\s$ maps non-edges to non-edges. So $\s$ is an automorphism of $\Ga$, and $G=\Sym([n])$ is a vertex-transitive automorphism group of $\Ga$. \begin{lemma}\label{vt} The graph $\Ga=\Ga_n$ is $G$-vertex-transitive and $G$-edge-transitive, but not $G$-arc-transitive. \end{lemma} \proof We consider the edges incident with the vertex $\a=(12,3)$. The stabilizer $G_\a=\Sym(\{1,2\})\times\Sym(\{4,5,\dots,n\})\cong\S_2\times\S_{n-3}$, and $G_\a$ acting on the neighborhood $\Ga(\a)$ has two orbits $\{(1i,2),(2i,1)\mid i>3\}$ and $\{(13,i),(23,i)\mid i>3\}$. Thus, $G$ is not transitive on the arcs of $\Ga$. Further, the element $g=(23i)$ maps $(1i,2)$ to $(12,3)$, and $(12,3)$ to $(13,i)$, so $g$ maps the edge $\{(1i,2),(12,3)\}$ to the edge $\{(12,3),(13,i)\}$. Since $\Ga$ is $G$-vertex-transitive, we conclude that $\Ga$ is $G$-edge-transitive. \qed Let $H$ be a subgroup of $G$, and $S$ be a subset of $G$. Define the {\it coset graph} of $G$ with respect to $H$ and $S$ to be the directed graph with vertex set $[G:H]$ and such that, for any $Hx$, $Hy\in V$, $Hx$ is connected to $Hy$ if and only if $yx^{-1}\in HSH$ and denote the digraph by $Cos(G,H,HSH)$. With the vertex $\a=(12,3)\in V_n$ and element $g=(234)\in G$, the graph $\Ga=\Ga_n$ can be described as a {\it coset graph} $\Cos(G,G_\a,G_\a\{g,g^{-1}\}G_\a)$, which has vertex set $[G:G_\a]=\{G_\a x\mid x\in G\}$ such that $G_\a x$ and $G_\a y$ are adjacent if and only if $yx^{-1}\in G_\a\{g,g^{-1}\}G_\a$. The right multiplication of each element $g\in G$ \[g:\ \ G_\a x\mapsto G_\a xg,\ \mbox{for all $x\in G$}\] induces an automorphism of $\Ga$. \begin{lemma}\label{arc-trans} If an automorphism $\t\in\Aut(G)$ normalizes $G_\a$ and $(G_\a\{g,g^{-1}\}G_\a)^\t=G_\a\{g,g^{-1}\}G_\a$, then $\t$ is an automorphism of $\Ga$. \end{lemma} \proof Since $\t$ normalizes $G_\a$, it induces a permutation on the vertex set $[G:G_\a]$. For any two vertices $G_\a x$ and $G_\a y$, we have \[\begin{array}{lll} G_\a x\sim G_\a y &\Longleftrightarrow & yx^{-1}\in G_\a\{g,g^{-1}\}G_\a\\ & \Longleftrightarrow & (yx^{-1})^\t\in(G_\a\{g,g^{-1}\}G_\a)^\t\\ & \Longleftrightarrow & y^\t(x^\t)^{-1}\in G_\a\{g,g^{-1}\}G_\a\\ & \Longleftrightarrow & (G_\a x)^\t=G_\a x^\t\sim G_\a y^\t=(G_\a y)^\t. \end{array}\] Thus, $\t$ is an automorphism of the graph $\Ga$. \qed \begin{lemma}\label{n=4,5} Both $\Ga_4$ and $\Ga_5$ are arc-transitive. \end{lemma} \proof Let $\a=(12,3)$, and $g=(234)$. Consider first the case $G=\S_4$. Then $G_\a=\Sym(\{1,2\})$, and $\Ga=\Cos(G,G_\a,G_\a \{g,g^{-1}\}G_\a)$. Let $\t$ be the inner-automorphism induced by the element $(34)\in G$. Then $\t$ normalizes $G_\a$ and $g^\t=g^{-1}$. By Lemma~\ref{arc-trans}, $\t$ is an automorphism of the graph. Further, for the edge $\{G_\a,G_\a g\}$, we have \[(G_\a,G_\a g)^{\t g}=(G_\a,G_\a g^{-1})^g=(G_\a g,G_\a),\] and so $\Ga$ is arc-transitive. Next, consider the case $G=\S_5$. Again let $\a=(12,3)$ and $g=(234)$. Then $G_\a=\Sym(\{1,2\})\times\Sym(\{4,5\})$, and $\Ga=\Cos(G,G_\a,G_\a \{g,g^{-1}\}G_\a)$. Let $\t$ be the inner-automorphism of $G$ induced by the element $(15)(24)\in G$. Then $\t$ normalizes $G_\a$ and reverses $g$. Arguing as above shows that $\Ga$ is arc-transitive. \qed However, we will show that $\Ga_n$ for $n\ge6$ are all half-transitive. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The parameters} Denote the graph $\Ga_n$ simply by $\Ga$ in the following. For vertices $\a=(i_1j_1,k_1)$ and $\b=(i_2j_2,k_2)$, we denote $\{i_1,j_1,k_1\}\cap\{i_2,j_2,k_2\}$ by $\a\cap\b$. Then $|\a\cap\b|=2$ if $\a$ and $\b$ are adjacent. \begin{lemma}\label{diam=3} The graph $\Ga=\Ga_n$ is of order ${n(n-1)(n-2)\over2}$, valency $4(n-3)$, girth $3$, and diameter $3$. \end{lemma} \proof As noticed above, each 3-subset $\{i,j,k\}$ corresponds to exactly three vertices $(ij,k)$, $(jk,i)$ and $(ik,j)$. Thus, the order $|V|$ of $\Ga$ equals $3{n\choose 3}={n(n-1)(n-2)\over2}$. By the definition of the graph $\Ga$, the neighborhood of the vertex $\a=(ij,k)$ is $\Ga(\a)=\{(ik,m), (jk,m), (im,j), (jm,i)|m\neq i,j,k\}$. Thus, $\Ga$ is of valency $4(n-3)$. Moreover, since $(jk,m)$ and $(jm,i)$ are adjacent, $\Ga$ is of girth 3. We next compute the distance $d(\a,\b)$ between two vertices $\a$ and $\b$. As $\Ga$ is a vertex-transitive graph, we take $\a=(12,3)$. We first consider a small case that $n=4$. Then $|V|=12$, and the neighborhood $\Ga(\a)=\{(14,2), (24,1), (13,4), (23,4)\}$. For other vertices except $(12,4)$, we have \[\Ga(\a)\cap\Ga(\b)=\left\{ \begin{array}{ll} \{(23,4)\}, & \mbox{if $\b=(13,2)$},\\ \{(13,4)\}, & \mbox{if $\b=(23,1)$},\\ \{(24,1)\}, & \mbox{if $\b=(14,3)$},\\ \{(14,2), (23,4)\}, & \mbox{if $\b=(34,1)$},\\ \{(14,2)\}, & \mbox{if $\b=(24,3)$},\\ \{(24,1),(13,4)\}, & \mbox{if $\b=(34,2)$},\\ \end{array} \right.\] and so $d(\a,\b)=2$. For $\b=(12,4)$, $\Ga(\a)\cap\Ga(\b)=0$. Furthermore, the sequence \[\mbox{$\a=(12,3)$, $(14,2)$, $(24,3)$, $\b=(12,4)$}\] is a path between $\a$ and $\b$ of length 3. Hence, $d(\a,\b)=3$, and thus, the graph $\Ga$ is of diameter 3. Now we treat the cases where $n\geq5$. Take $\a=(12,3)$, and let $\b=(ij,k)$. \vskip0.08in \noindent{\bf Case 1.} Assume first that $i,j,k\geq 4$. If a vertex $\g=(i'j',k')$ is adjacent to both $\a$ and $\b$, then $|\g\cap \a|=2$ and $|\g\cap\b|=2$, which is not possible. Thus, $d(\a,\b)$ is at least 3. On the other hand, the sequence \[\mbox{$\a=(12,3)$, $(1i,2)$, $(ik,1)$, $\b=(ij,k)$}\] is a path between $\a$ and $\b$ of length 3. Hence, $d(\a,\b)=3$. \vskip0.08in \noindent{\bf Case 2.} Next, consider the case where $|\a\cap\b|=1$. Suppose that $\b=(ij,3)$, where $i,j\ge4$. Then the sequence $\a$, $(1i,2)$, $(i3,1)$, $\b$ is a path between $\a$ and $\b$, and hence $d(\a,\b)\le 3$. As mentioned above, \[\Ga(\a)=\{(1i',2),(2i',1),(13,i'),(23,i') \mid i'>3\},\] and similarly, \[\Ga(\b)=\{(ij',j),(jj',i),(3i,j'),(3j,j')\mid j'\notin\{3,i,j\}\}.\] Thus, $\Ga(\a)\cap\Ga(\b)=\emptyset$, and so $d(\a,\b)=3$. Assume now that $k\neq 3$. Then $\b=(1i,k)$, $(2i,k)$, $(3i,k)$, $(ij,1)$ or $(ij,2)$, where $i,j,k\geq 4$. In each of these cases, $d(\a,\b)=2$ because \[\Ga(\a)\cap\Ga(\b)=\left\{ \begin{array}{ll} \{(1k,2),(13,i),(2i,1)\}, & \mbox{if $\b=(1i,k)$},\\ \{(2k,1),(23,i),(1i,2)\}, & \mbox{if $\b=(2i,k)$},\\ \{(31,i),(32,i)\}, & \mbox{if $\b=(3i,k)$},\\ \{(1i,2),(1j,2)\}, & \mbox{if $\b=(ij,1)$},\\ \{(2i,1),(2j,1)\}, & \mbox{if $\b=(ij,2)$}.\\ \end{array} \right.\] \vskip0.08in \noindent{\bf Case 3.} We then treat the case where $|\a\cap\b|=2$. Assume that $k=3$. Then $\b=(1i,3)$ or $(2i,3)$, where $i\geq 4$. If $\b=(1i,3)$, then $\Ga(\a)\cap\Ga(\b)=\{(13,m), (2i,1)\mid 4\le m\le n, m\not=i\}$, and thus $d(\a,\b)=2$. Similarly, if $\b=(2i,3)$, there exists $n-3$ paths of length 2 between $\a$ and $\b$, and so $d(\a,\b)=2$. Suppose that $k\neq 3$. Then $\b=(12,k)$, $(1i,2)$, $(2i,1)$, $(13,k)$, $(23,k)$, $(3i,1)$, $(3i,2)$, where $i,k\ge4$. If $\b=(12,k)$, then $\Ga(\a)\cap\Ga(\b)=\{(1m,2), (2m,1)\mid 4\le m\le n, m\not=k\}$, and so $d(\a,\b)=2$. For these vertices $\b=(1i,2)$, $(2i,1)$, $(13,k)$, or $(23,k)$, we have $\b\in\Ga(\a)$, and thus $d(\a,\b)=1$. If $\b=(3i,1)$, $\Ga(\a)\cap\Ga(\b)=\{(13,m), (23,i), (1i,2)|4\le m\le n,m\not=i\}$, and hence $d(\a,\b)=2$. Similarly, if $\b=(3i,2)$, $\Ga(\a)\cap\Ga(\b)=\{(23,m), (13,i), (2i,1)|4\le m\le n,m\not=i\}$, and so $d(\a,\b)=2$. \vskip0.08in \noindent{\bf Case 4.} Let $|\a\cap\b|=3$. Then $\b=(23,1)$ or $(13,2)$. For $\b=(23,1)$, we have $d(\a,\b)=2$ as $(13,m)$ is adjacent to both $\a$ and $\b$, and thus, there are exactly $n-3$ paths of length 2 between $\a$ and $\b$, where $m\neq 1,2,3$. Similarly, if $\b=(13,2)$, $d(\a,\b)=2$ because there exist exactly $n-3$ paths $\a$, $(23,m)$, $\b$ of length 2 between $\a$ and $\b$, where $m\neq 1,2,3$. Thus, $\Ga=\Ga_n$ is of diameter 3. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Quotients} The action of $G=\Sym([n])$ on $V_n$ has three types of blocks as below \[\begin{array}{l} B_k=\{(ij,k)\mid i,j\in[n]\setminus\{k\}\},\ \mbox{size ${n-1\choose2}$},\\ B_{ij}=\{(ij,k)\mid k\in[n]\setminus\{i,j\}\},\ \mbox{size $n-2$},\\ B_{ijk}=\{(ij,k),(jk,i),(ki,j)\},\ \mbox{size 3}. \end{array}\] Let $\calB_1=B_k^G$, $\calB_2=B_{ij}^G$, and $\calB_3=B_{ijk}^G$. Then $|\calB_1|=n$, $|\calB_2|={n\choose2}$, and $|\calB_3|={n\choose 3}$. \begin{lemma}\label{partition} If $n\ge7$, then $V=V_n$ has exactly three non-trivial $G$-invariant partitions: $\calB_1$, $\calB_2$ and $\calB_3$. \end{lemma} \proof For the vertex $\b=(23,1)$, the stabilizer $G_\b=\Sym(\{2,3\})\times\Sym([n]\setminus\{1,2,3\})$, and $G_\b$ is contained in $G_{B_1}$, $G_{B_{23}}$ and $G_{B_{123}}$. Moreover, these three subgroups are maximal in $G$ and are the only proper subgroups of $G$ which properly contain $G_\b$. Thus, $\calB_1$, $\calB_2$ and $\calB_3$ are the only block systems of $G$ acting on $V_n$. \qed By Lemma \ref{partition}, we have three block systems $\calB_i$ with $i=1$, 2 or 3, and we have three quotient graph $\Ga_{\calB_i}$. Clearly, the induced action of $G$ on $\calB_i$ is equivalent to the action of $G$ on $[n]^{\{i\}}$, where $i=1$, 2 or 3. We thus identify $\calB_1$ with $[n]$, $\calB_2$ with $[n]^{\{2\}}$, and $\calB_3$ with $[n]^{\{3\}}$. The quotient graph $\Ga_{\calB_1}=\K_n=\J(n,1)$. For $\Ga_{\calB_2}$, two vertices $B_{ij}$ and $B_{i'j'}$ are adjacent if and only if $|\{i,j\}\cap\{i',j'\}|=1$, and so $\Ga_{\calB_1}=\J(n,2)$. For $\Ga_{\calB_3}$, two vertices $B_{ijk}$ and $B_{i'j'k'}$ are adjacent if and only if $|\{i,j,k\}\cap\{i',j',k'\}|=2$. Thus, we have the following lemma. \begin{lemma}\label{quotient} The quotient graph $\Ga_{\calB_i}$ is the Johnson graph $\J(n,i)$, where $i=1$, $2$ or $3$. \end{lemma} For a quotient graph $\Ga_\calB$, let $B,B'\in\calB$ be adjacent in $\Ga_\calB$. The {\it induced subgraph} $[B\cup B']$ of $\Ga$ over $B\cup B'$ is the graph with vertex set $B\cup B'$ and edge set $E_0=\{\{u,v\}\in E\mid u,v\in B\cup B'\}$. Then $[B\cup B']$ is a bipartite graph with biparts $B$ and $B'$; denoted by $[B,B']$. We next determine the induced subgraph $[B,B']$ for the quotient graph $\Ga_{\calB_i}$. For a graph $\Sig=(V,E)$, the {\it vertex-edge incidence graph} is the bipartite graph with biparts $V$ and $E$ such that two vertices $v\in V$ and $w\in E$ are adjacent if and only if $v,w$ are incident in $\Sig$. This incidence graph is also called the {\it subdivision} of $\Sig$. \begin{lemma}\label{B-B'-1} Let $B,B'\in\calB_1$ be adjacent in $\Ga_{\calB_1}$. Then the induced subgraph $[B,B']$ consists of $2$ copies of the subdivision of $\K_{n-2}$. \end{lemma} \proof Since $(23,1)\in B_1$ is adjacent to $(34,2)\in B_2$, the vertices $B_1$ and $B_2$ are adjacent in the quotient $\Ga_{\calB_1}$. The edges of the induced subgraph $[B_1,B_2]$ are \[\{\{(2i,1),(ij,2)\}\mid 3\le i\le n,\ j\not=i,1,2\}\cup \{\{(1i,2),(ij,1)\}\mid 3\le i\le n,\ j\not=i,1,2\},\] which form two copies of the subdivision of $\K_{n-2}$. \qed A {\it star} $\K_{1,m}$ is a bipartite graph with $m+1$ vertices, in which there is one vertex that is adjacent to all other $m$ vertices. In particular, $\K_{1,2}$ is a path of length 2. \begin{lemma}\label{B-B'-2} Let $B,B'\in\calB_2$ be adjacent in $\Ga_{\calB_2}$. Then the induced subgraph $[B,B']$ consists of $2$ copies of the star $\K_{1,n-3}$. \end{lemma} \proof Since $(12,3)\in B_{12}$ is adjacent to $(23,4)\in B_{23}$, the vertices $B_{12}$ and $B_{23}$ are adjacent in the quotient $\Ga_{\calB_2}$. The edges of the induced subgraph $[B_{12},B_{23}]$ are $\{\{(12,3)$, $(23,i)\}\mid i\ge4\}\cup\{\{(23,1),(12,j)\}\mid j\ge4\}$, which form two stars $\K_{1,n-3}$. \qed \begin{lemma}\label{B-B'-3} Let $B,B'\in\calB_3$ be adjacent in $\Ga_{\calB_3}$. Then the induced subgraph $[B,B']$ consists of $2$ paths of length $2$. \end{lemma} \proof For the blocks $B=\{(12,3),(23,1),(31,2)\}$ and $B'=\{(12,4),(24,1),(41,2)\}$, the induced subgraph $[B,B']$ has 4 edges \[\mbox{$\{(12,3),(14,2)\}$, $\{(12,3),(24,1)\}$, $\{(12,4),(13,2)\}$, $\{(12,4),(32,1)\}$.} \] These edges form two paths of length 2: \[(23,1),(12,4),(13,2),\ \ \mbox{and}\ (24,1),(12,3),(14,2).\] Thus, $[B,B']=2\K_{1,2}$. \qed \section{The automorphism group} In this section, we determine the automorphism group $\Aut\Ga$. \begin{lemma}\label{al-simple} Let $n\ge7$, and let $X$ be a subgroup such that $G\leq X\leq \Aut\Ga$. Then $X$ is almost simple, and if $X\not=G$, then $X$ is primitive on $V$. \end{lemma} \proof Let $M$ be a minimal normal subgroup of $X$. Suppose that $M$ is intransitive on $V$. Let $\calB$ be the set of $M$-orbits on $V$. Then $\calB$ is $X$-invariant and $G$-invariant. By Lemma~\ref{partition}, $\calB=\calB_i$ with $i=1$, 2 or 3. For $B_i\in\calB_i$, we have that $G_{B_1}^{B_1}=\S_{n-1}$, $G_{B_2}^{B_2}=\S_{n-2}$, and $G_{B_3}^{B_3}=\S_3$. Thus, $G_{B_i}^{B_i}$ is primitive, and so is $X_{B_i}^{B_i}$. Let $K=X_{(\calB)}$, the kernel of $X$ acting on $\calB$. Suppose that $K\not=1$. Then $1\not=K^B\lhd X_B^B$, and so $K^B$ is transitive as $X_B^B$ is primitive. Let $B'\in\calB$ be adjacent in $\Ga_\calB$ to $B$. Then $K$ is transitive on $B'$, and since $|B|=|B'|$, we conclude that the induced subgraph $[B,B']$ is regular, which is a contradiction by Lemmas~\ref{B-B'-1}-\ref{B-B'-3}. Thus, $K=1$, and so $M=1$, which is a contradiction. So $M$ is transitive on $V$, and $X$ is quasiprimitive on $V$. Further, $M$ is non-abelian since $|V|=3{n\choose3}$. Now let $M=T_1\times T_2\times\ldots\times T_l$, where $l\geq1$, and $T_1\cong T_2\cong\ldots\cong T_l$ are non-abelian simple groups. Then $M\cap G\lhd G$, and so $M\cap G=1$, $\A_n$ or $\S_n$. Suppose that $M\cap G=1$. Let $Z=MG=M{:}G$. If $Z$ is imprimitive on $V$, then a block system $\calB=\calB_1$, $\calB_2$ or $\calB_3$. Hence $Z\cong Z^\calB\le G^{\calB}\cong\S_n$, which is not possible. Thus, $Z$ is primitive on $V$, and $G$ does not centralize $M$. By O'Nan-Scott's theorem (see \cite{Dixon-book}), we have that $l\ge n$, and ${n(n-1)(n-2)\over 2}=|V|=m^l$ or $m^{l-1}$ where $m\ge5$, which is not possible. Therefore, $M\cap G=\A_n$ or $\S_n$, and letting $L=\soc(G)=\A_n$, we have $L\leq M$. Since $L$ is non-abelian simple, $L$ is contained in a simple group $T_i$, say $T_1$. Hence, $T_1$ is transitive on $V$. If $l\ge2$, then as $T_2$ centralizes $T_1$, we have that $T_2$ is semiregular on $V$. Then $|V|$ divides $|T_1|$, and $|T_2|=|T_1|$ divides $|V|$. So $T_1$ is regular on $V$, and since $G$ is transitive on $V$, $L\leq T_1$ is semiregular with at most 2 orbits. Since $T_1$ has no subgroup of index 2 and $G/L\cong\ZZ_2$, we have that $L=T_1$ is regular on $V$, which is a contradiction. Thus, $M=T_1$ is simple and $L\leq M$. Assume that there exists another minimal normal subgroup $N$ of $X$ such that $N\neq M$. Then $M\cap N=1$; however, the above argument with $N$ in the place of $M$ shows that $L\leq N$. So $M\cap N\ge L$, which is a contradiction. Therefore, $M$ is simple and the unique minimal normal subgroup of $X$, and hence $X$ is almost simple. Suppose that $X>G$ and $X$ is imprimitive on $V$. Let $\calB$ be a block system for $X$ on $V$. Then $\calB$ is a block system for $G$ on $V$. By Lemma~\ref{partition}, $\calB=\calB_i$ where $i=1$, 2 or 3, and by Lemma~\ref{quotient}, $\Ga_\calB=\J(n,i)$. As noticed in the Introduction, $\Aut\Ga_\calB=\S_n$, and so $\S_n\cong G