8 s-arc-transitive digraph

1-arc-transitive digraph

Definition

We say $\Gamma =(V,E)$ is an arc-transitive digraph, if $G\le \mathrm{Aut}(\Gamma )$ is transitive on the edge-set.

Note that a star ${\vec{K}}_{1,r}$ is not vertex transitive. And $G$ is transitive on $V$ if $\Gamma$ is regular, i.e., in-valency of each point is equal. Thus $\Gamma$ is an orbital graph of $G$ on $V$, that is, a graph whose vertex set is $V$ and edge set is an orbit of $G$ acting on $V\times V$.

Definition

Let ${\Gamma }^{\ast }$ be the paired orbital graph of $\Gamma$, i.e. if $\Gamma =(V,(u,v{)}^G)$, then ${\Gamma }^{\ast }=(V,(v,u{)}^G)$. Let ${\Gamma }^{+}(v)=\{w\in V:(v,w)\in E\}$ be the out-neighbor of $v$ and ${\Gamma }^{-}(v)=\{w\in V:(w,v)\in E\}$ be the in-neighbor of $v$.

Lemma

A regular digraph $\Gamma =(V,E)$ is $G$-arc-transitive iff $G\le \mathrm{Aut}(\Gamma )$ is transitive on $V$ and $G_v$ is transitive on ${\Gamma }^{+}(v)$ (or ${\Gamma }^{-}(v)$).

\begin{proof} Easy. \end{proof}

2-arc-transitive digraph

Definition

We say $\Gamma =(V,E)$ is a $(G,2)$-arc-transitive digraph if $\Gamma$ has $2$-arcs and $G\le \mathrm{Aut}(\Gamma )$ is transitive on the set of $2$-arcs of $\Gamma$.

Lemma

Let $\Gamma =(V,E)$ be a $G$-vertex-transitive digraph. Then $G$ is $2$-arc-transitive on $\Gamma$ iff

• $G_v$ is transitive on ${\Gamma }^{+}(v)$;
• $G_{u,v}$ is transitive on ${\Gamma }^{+}(v)$ where $(u,v)$ is an arc of $\Gamma$.

\begin{proof} The proof is similar to lemma 1. \end{proof}

Proposition

Let $\Gamma =(V,E)$ be a connected $G$-arc-transitive digraph which is not undirected. Then $\Gamma$ is $(G,2)$-arc-transitive iff $G_v=G_{uv}{G}_{vw}$ where $(u,v,w)$ is a $2$-arc.

\begin{proof} Suppose $\Gamma$ is $(G,2)$-arc-transitive. Let $(u,v,w)$ be a $2$-arc. Then $(u,v,x)$ is a $2$-arc for any $x\in {\Gamma }^{+}(v)$. Thus there is a $g\in G$ such that $(u,v,w{)}^g=(u,v,x)$. By Frattini’s argument, $G_v=G_{uv}{G}_{vw}$.

Conversely, assume $G_v=G_{uv}{G}_{vw}$ for a $2$-arc $(u,v,w)$. Let $(x,y,z)$ be a $2$-arc. Since $G$ is arc-transitive, there is a $g\in G$ such that $(x,y{)}^g=(u,v)$. Let $w^{\prime }=z^g$. Then $w^{\prime }\in {\Gamma }^{+}(v)$. Since $G_v=G_{uv}{G}_{vw}$, $G_{uv}$ is a transitive subgroup of $G_v$ on ${\Gamma }^{+}(v)$. Then there is a $h\in G_{uv}$ such that $w^{\prime h}=w$. Hence $(x,y,z{)}^{gh}=(u,v,w)$. \end{proof}

s-arc-transitive digraph

Proposition

Let $\Gamma =(V,E)$ be a connected $G$-arc-transitive digraph which is not undirected. Then $\Gamma$ is $(G,s)$-arc-transitive iff $G_{v_i}=G_{v_0\cdots v_i}{G}_{v_{i}w}$ where $(v_0,\cdots ,v_i)$ is an $i$-arc, $i<s$.

\begin{proof} Assume $\Gamma$ is $(G,s)$-arc-transitive. Then $G_{v_i}$ is transitive on ${\Gamma }^{+}(v_i)$ and so for $G_{v_0\cdots v_i}$. By Frattini’s argument we have $G_{v_i}=G_{v_0\cdots v_i}{G}_{v_{i}w}$.

Conversely, suppose $G_{v_i}=G_{v_0\cdots v_i}{G}_{v_{i}w}$ for any $i<s-1$. Take any $2$-arcs $(u_0,\cdots u_s)$ and $(w_0,\cdots ,w_s)$. By $\Gamma$ being $(G,2)$-arc-transitive, there is $g_1$ s.t. $(u_0,u_1,u_2{)}^{g_1}=(w_0,w_1,u_2^{\prime })$. Since $G_{u_1}=G_{u_0{u}_1}{G}_{u_1{u}_2^{\prime }}$, $G_{u_0{u}_1}$ is transitive on ${\Gamma }^{+}(u_1)$ and so there is $g_2$ s.t. $(u_0,u_1,u_2,u_3{)}^{g_1{g}_2}=(w_0,w_1,w_2,u_3^{\prime })$. Repeat the procedure and the proof is completed. \end{proof}

Constructions

A trivial example of highly-arc-transitive digraph is a lexicographical product $C_n[\overline{K_m}]$, whose automorphism group is $S_m\wr C_n$ and so is $(n-1)$-arc-transitive.

In the following part, we give a non-trivial construction of $s$-arc-transitive digraph.

Case 1: $s=2$

Recall the definition of coset graph. Define $\Gamma =\mathrm{Cos}(G,H,HgH)$, where $V=[G:H]$ and $(x,y)$ is an arc iff $y{x}^{-1}\in HgH$. Since $\Gamma$ is directed, we know $g^2\notin HgH$.

Let $G=N:⟨g⟩$, where $N=⟨a_0⟩\times \cdots \times ⟨a_{n-1}⟩\cong {\mathbb{Z}}_{p^2}^n$ and $a_i^g=a_{i+1}$, reading $i+1(\mathrm{mod}n)$. Let $H=⟨a_1⟩\times ⟨a_2⟩\times ⟨a_3^p⟩$ and $\Gamma =\mathrm{Cos}(G,H,HgH)$.

Claim 1: $\Gamma$ is $(G,2)$-arc transitive. Label $H$ on $v$ and $H{g}^{-1},Hg$ on $u,w$, respectively. Then $(u,v,w)$ is an $2$-arc and $G_v=H$. Note that

$$G_u=H^{g^{-1}}=⟨a_0⟩\times ⟨a_1⟩\times ⟨a_2^p⟩$$

and

$$G_w=H^g=⟨a_2⟩\times ⟨a_3⟩\times ⟨a_4^p⟩.$$

Thus $G_v=G_{uv}{G}_{vw}$ and so $\Gamma$ is $(G,2)$-arc transitive by ^e1odoe.

Claim 2: $G_v^{{\Gamma }^{-}(v)}\ncong G_v^{{\Gamma }^{+}(v)}$. Since ${\Gamma }^{+}(v)=\{Hgh:h\in H\}=[G_v:G_{vw}]$, $G_v$ acts on ${\Gamma }^{+}(v)$ is equivalent to $G_v$ acts on $[G_v:G_{vw}]$ by coset action. Then $G_v^{{\Gamma }^{+}(v)}\cong G_v/K$, where $K$ is the kernel of $G_v$ on ${\Gamma }^{+}(v)$, i.e. the core of $G_{vw}$ in $G_v$. As $G_v$ is abelian, ${\mathrm{Core}}_{G_v}(G_{vw})=G_{vw}$. So $G_v^{{\Gamma }^{+}(v)}\cong G_v/G_{vw}\cong ⟨a_1⟩\cong {\mathbb{Z}}_{p^2}$. Similarly, $G_v^{{\Gamma }^{-}(v)}\cong G_v/G_{uv}\cong ⟨\overline{a_2}⟩\times ⟨a_3^p⟩\cong {\mathbb{Z}}_p\times {\mathbb{Z}}_p$, completing the proof.

Case 2: for a general $s$

Let $G=N:⟨g⟩$, where $N=⟨a_0⟩\times \cdots \times ⟨a_{n-1}⟩\cong {\mathbb{Z}}_{p^2}^n$ and $a_i^g=a_{i+1}$, reading $i+1(\mathrm{mod}n)$. Let $H=⟨a_1⟩\times \cdots \times ⟨a_s⟩\times ⟨a_{s+1}^p⟩$ and $\Gamma =\mathrm{Cos}(G,H,HgH)$. Claim that $\Gamma$ is $(G,s)$-arc transitive.

Label $H$ on $v$ and let $v_0=v$, $v_j=v_0^{g^j}$. Then $(v_0,\cdots ,v_i)$ is an $i$-arc. Note that $G_{v_i}=H^{g^i}=⟨a_{i+1}⟩\times \cdots \times ⟨a_{i+s}⟩\times ⟨a_{i+s+1}^p⟩$, $G_{v_0\cdots v_i}=⟨a_{i+1}⟩\times \cdots \times ⟨a_s⟩\times ⟨a_{s+1}^p⟩$ and $G_{v_{i}x}=⟨a_{i+2}⟩\times \cdots \times ⟨a_{s+i}⟩\times ⟨a_{s+i+1}^p⟩$ with $x=v_{i+1}$. Then $G_{v_i}=G_{v_0\cdots v_i}{G}_{v_{i}x}$ for any $i<s$. Similarly, we can prove that $\Gamma$ is $(G,s)$-arc-transitive and $G_v^{{\Gamma }^{-}(v)}\ncong G_v^{{\Gamma }^{+}(v)}$.

Remark.

• If $H=⟨a_1⟩\times \cdots \times ⟨a_{s+1}⟩$ instead of $⟨a_1⟩\times \cdots \times ⟨a_s⟩\times ⟨a_{s+1}^p⟩$, then $G_v^{{\Gamma }^{+}(v)}\cong G_v^{{\Gamma }^{-}(v)}$.
• This example is not isomorphic to donut, as $G$ is not a subgroup of $S_m\wr C_n$.
• $M:={\mathbb{Z}}_p^n⊲G$ is a normal subgroup. The quotient graph ${\Gamma }_M$ is called Praeger graph. Praeger-Xu graph is also mentioned, although I did not understand its definition.