5.2 Construction of half-transitive graph

Half transitive graphs

Half transitive graphs are vertex transitive and edge transitive but not arc transitive.

The smallest example of half transitive graph has $27$ vertices and valency $4$. Here is another example, which gives a series of half transitive graph.

Let $p$ be an odd prime and $m\ge 2$. Let $G=⟨a⟩:⟨b⟩\cong C_{p^m}:C_p$ and $a^b=a^{1+p^{m-1}}$. Let $S=\{ba,(ba{)}^{-1},b{a}^{-1},(b{a}^{-1}{)}^{-1}\}$, define $\Gamma =\mathrm{Cay}(G,S)$.

$\Gamma$ is edge-transitive

$\Gamma$ is edge transitive. Oberve $\tau :a\mapsto a^{-1},b\mapsto b$ is an automorphism of $G$ and $\tau \in \mathrm{Aut}(G,S)$ such that $\hat{G}:⟨\tau ⟩$ is edge transitive.

$\Gamma$ is not arc-transitive

Claim: $\Gamma$ is not arc transitive (it will be implied by the fact that $Aut(\Gamma )=\hat{G}:⟨\tau ⟩$).

Let $X=\mathrm{Aut}(\Gamma )$ and take $\alpha =i{d}_G$. Viewing $\alpha$ be a vertex of $\Gamma$, then $X=G{X}_{\alpha }$. $X_{\alpha }^{\Gamma (\alpha )}\le S_4$ and $⟨S⟩=G$ yields $X_{\alpha }$ is a $\{2,3\}$-group. So $X$ is a $\{2,3,p\}$-group. (In general, if $X_{\alpha }^{\Gamma (\alpha )}\le S_n$, then $X_{\alpha }$ is a $\pi$-group where $\pi$ is a subset of $\pi (n!)$.)

Prove that $\mathrm{Aut}(\Gamma )=\hat{G}:⟨\tau ⟩$

Next our discussion divides into two cases, one is $p=3$ and another is $p>3$.

Case 1: $p>3$

Claim: $Aut(G,S)$ is not transitive on $S$. Otherwise, there exists $\sigma \in Aut(G,S)$ such that $(ba{)}^{\sigma }=(ba{)}^{-1}$, $(b{a}^{-1}{)}^{\sigma }=(b{a}^{-1}{)}^{-1}$. Then $a^{\sigma }=a^{-1+p^{m-1}}$, $|\sigma |=p$, contradiction.

So $Aut(G,S)$ has two orbits on $S$: $S=\{ba,b{a}^{-1}\}\cup \{(ba{)}^{-1},(b{a}^{-1}{)}^{-1}\}$. And by $Aut(G,S)\le S_4$, $|Aut(G,S)|=2$. Thus $Aut(G,S)=⟨\tau ⟩$.

Define $N:=O_p(X)$ which is the largest normal p-subgroup of $X$. $N$ is half-transitive on $V\Gamma$, $N_{\alpha }◃X_{\alpha }$ and $N_{\alpha }^{\Gamma (\alpha )}◃X_{\alpha }^{\Gamma (\alpha )}\le S_4$. Since all transitive or half-transitive subgroups of $S_4$ have a normal 2-subgroup, $N_{\alpha }^{\Gamma (\alpha )}=1$. By $\Gamma$ connected, $N_{\alpha }=1$ and so $N$ is semi-regular on $V\Gamma$. Then we will discuss two cases, depending on whether $N$ is transitive on $V\Gamma$ or not.

Case 1.1: $O_p(X)$ is transitive

Now further assume $N$ is vertex transitive. Then $N$ is regular on $V\Gamma$ and so $N=G$, $X_{\alpha }=\mathrm{Aut}(G,S)$. So $G$ is a normal subgroup of $X$.

As we have known $Aut(G,S)=⟨\tau ⟩$ , the following lemma yields $Aut(\Gamma )=\hat{G}:Aut(G,S)=\hat{G}:⟨\tau ⟩$.

Lemma. Suppose $\Gamma =Cay(G,s)$. Then

• $N_{Aut(\Gamma )}(\hat{G})=\hat{G}:Aut(G,S);$
• $\hat{G}{C}_{Aut\Gamma }(\hat{G})=\hat{G}:Inn(G,S).$

Case 1.2: $O_p(X)$ is intransitive

Now assume $N$ is not vertex transitive. As $N$ is a normal subgroup, the orbits of $N$ form a block system of $X$, denoted by $\mathcal{B}$. Let $K:=X_{\mathcal{B}}$ be the kernel of $X$ on $\mathcal{B}$. By the definition of $\mathcal{B}$, $N⊲K$ and $K=N{K}_{\alpha }$, where $\alpha \in B\in \mathcal{B}$. Subcases are divided depending on whether $X/N$ is solvable or not.

Case 1.2.1: $X/N$ is solvable

Useless argument: ${\Gamma }_B$ cycle and $K_{\alpha }$ 2-group

Claim 1: ${\Gamma }_{\mathcal{B}}$ is a cycle.

Consider ${\Gamma }_N=(\mathcal{B},E_N)$, then ${\Gamma }_N={\Gamma }_K$ are all edge transitive (Notice that $X/N$ may not be faithful on the vertex set of ${\Gamma }_{\mathcal{B}}={\Gamma }_K$).

Suppose $M$ is a minimal normal subgroup of $X/N$, then $M\cong C_r^e$ where $r\in \{2,3\}$. As $M$ is a normal subgroup of $X/N$, $M$ is half-transitive on $\mathcal{B}$. $|\mathcal{B}|||G|$ yields $|\mathcal{B}|$ is a power of $p$. If $M$ does not fix all blocks of $\mathcal{B}$, then $|M|/|M_{B_0}|=|B_0^M|$ is divided by $p$ and so for $|M|$, contradiction.

Therefore, $M$ fixes all blocks of $\mathcal{B}$ and so $M\le K$. Thus $L:=NM$ is a normal subgroup of $K$. As $N_{\alpha }$ is trivial, there is $L_{\alpha }=M_{\alpha }$. Hence $M_{\alpha }⊲K_{\alpha }⊲X_{\alpha }$.

If $K_{\alpha }$ acting on $\Gamma (\alpha )$ is transitive, then $\mathrm{val}{\Gamma }_K=1$ and $|V{\Gamma }_K|=2$, which is impossible by $|V\Gamma |$ odd. If $K_{\alpha }$ acting on $\Gamma (\alpha )$ is trivial, then $K_{\alpha }=\{1\}$ as $\Gamma$ is connected and $⟨S⟩=G$. Then $K$ is semi-regular on $V\Gamma$ and $|K|||G|$, thus $K=\{1\}$. Hence $N\le K$ is also trivial and so $p=3$, contradiction.

Therefore, the valency of ${\Gamma }_K$ is not $1$ or $4$. Thus $\mathrm{val}{\Gamma }_K=2$ and so ${\Gamma }_K$ is a cycle.

Claim 2: $K_{\alpha }$ is a 2-group.

By the same argument, $M_{\alpha }$ is non-trivial. If $r=3$, then $3$ divides the order of $K_{\alpha }$. $|K_{\alpha }|\ge 3$ yields length of orbits of $K$ is greater than or equal $3$ and so $K_{\alpha }$ is transitive on $\Gamma (\alpha )$, contradiction. Hence $K_{\alpha }$ is a $2$-group.

If $r=3$, then $3$ divides the order of $K_{\alpha }$. $|K_{\alpha }|\ge 3$ yields length of orbits of $K$ is greater than or equal $3$. Then the valency of ${\Gamma }_{\mathcal{B}}$ is $1$ and so $|\mathcal{B}|=2$, which is impossible by $|G|$ odd.

Hence $K_{\alpha }$ is a $2$-group. By the same argument, we can prove $K_{\alpha }$ is intransitive on $V\Gamma$, then valency of ${\Gamma }_{\mathcal{B}}$ is $2$ or $4$.

If $\mathrm{val}({\Gamma }_{\mathcal{B}})=4$, $K_{\alpha }$ acting on $\Gamma (\alpha )$ is trivial. Then $⟨S⟩=G$ yields $K_{\alpha }$ is trivial and $K=N$. (what happens then?)

---

really useful part…

Claim 3: $X=\hat{G}:⟨\tau ⟩$.

First, we will show a lemma.

Lemma. Let $H$ be a $p$-group and $\Phi (H)$ be the Frattini subgroup of $H$, then there is a normal $p$-subgroup $Q$ of $\mathrm{Aut}(H)$ such that$\mathrm{Aut}(H)\cong Q:A$where $A\le \mathrm{Aut}(H/\Phi (H))$.

Proof. Let $L=\Phi (H)$. $H$ is a $p$-group hence $H/L$ is an elementary abelian $p$-group $C_p^e$ where $e$ is a positive integer. It is known that $e$ equals to the cardinality of minimal generating sets of $H$. For convenience, let $G$ be $\mathrm{Aut}(H)$. Then $G$ can acts on $H/L$ by the natural action, hence there is $G/Q\le \mathrm{Aut}(H/L)$

where $Q$ is the kernal of the action. By the Theorem of P.Hall, for all $q\in Q$, the order of $q$ is a power of $p$ hence $Q$ is a $p$-group. $■$

Note that $X=G{X}_{\alpha }$ where $G$ is metacyclic and $X_{\alpha }$ is $\{2,3\}$-group. Since $N=O_p(X)$ is a subgroup of $x^{-1}Gx$ where $x\in X$, $N$ is metacyclic.

Now consider the following equation:

$$(X/\Phi (N))/(N/\Phi (N))\cong X/N.$$

By the above lemma, there is a $p$-group $Q$ such that $X<\mathrm{Aut}N\le Q:\mathrm{Aut}(N/\Phi (N))$. Since $N=O_p(X)$, $Q\le N$. Thus $X/N\le \mathrm{Aut}(N/\Phi (N))$. Since $N/\Phi (N)$ is elementary abelian and $N$ is metacyclic, $\mathrm{Aut}(N/\Phi (N))\cong C_{p-1}$ or $\mathrm{GL}(2,p)$.

If $N/\Phi (N)$ is cyclic, then $X/N\le C_{p-1}$ imposing $N=G$ is transitive on $V\Gamma$, contradiction. Thus $\mathrm{Aut}(N/\Phi (N))\cong \mathrm{GL}(2,\mathrm{p})$ and $X/N\le \mathrm{GL}(2,\mathrm{p})$.

Let $\overline{X}=X/N$ and $L:=(\overline{X}\cap SL(2,p))/(\overline{X}\cap Z(SL(2,p)))$. Then $L$ is a subgroup of $PSL(2,p)$ whose Sylow $p$-subgroup is nontrivial and nonnormal, (otherwise $G=L$ or $O_p(X)=L.P\ne L$ where $P$ is the normal $p$-subgroup) otherwise $\hat{G}⊲X$ and the proof is completed. By Dickson’s theorem page 256, the only subgroup with these properties is $\mathrm{PSL}(2,p)$ itself. Thus $\overline{X}\ge SL(2,p)$, which is contradictory to $X$ is solvable.

So far we have proved if $p\ge 5$ and $X/N$ is solvable, then $\hat{G}$ is normal in $X$ hence $X=\hat{G}:⟨\tau ⟩$.

---

Case 1.2.2 $X/N$ is non-solvable

Noting that $X/N$ is a $\{2,3,p\}$-group, each non-solvable composition factor $T$ is$$ A_5,A_6,\mathrm{PSL}_2(7),\mathrm{PSL}_2(8),\mathrm{PSL}_2(17),\mathrm{PSL}_3(3),PSU_3(3),PSU_4(2).

In this case, $K=N$. Otherwise, (quotient graph is a circle) And $X=N:(X/N)$, where $N$ is metacyclic $p$-group and $X/N$ acts on $N$ faithfully. So $X/N\leq\mathrm{Aut}(Z_p^2)=\mathrm{GL}(2,p)$. It follows that $(p,T)$ is$$ (5,\mathrm{SL}_2(5)),(7,\mathrm{SL}_2(7)),(17,\mathrm{SL}_2(17)).

Case 2: $p=3$