Alice Devillers, Cai Heng Li and Cheryl Praeger and I submitted a paper last week entitled `An infinite family of biquasiprimitive 2-arc transitive cubic graphs‘. In this post I will outline the program into which the paper fits.  Some of this was covered in my 33ACCMCC plenary talk.

A s-arc in a graph is an (s+1)-tuple $(v_0,v_1,\ldots,v_s)$ of vertices such that $v_i$ is adjacent to $v_{i+1}$ but $v_{i+2}\neq v_i$, that is, it is a path in the graph which cannot immediately go back upon itself. A graph $\Gamma$ is called s-arc-transitive if $\mathrm{Aut}(\Gamma)$ acts transitively on the set of s-arcs in $\Gamma$. If each vertex has valency at least two then every vertex has an s-arc starting at it and every (s-1)-arc can be extended to an s-arc. Hence if $\Gamma$ is s-arc-transitive then it is also (s-1)-arc-transitive. In particular, $\mathrm{Aut}(\Gamma)$ acts transitively on the set of arcs of $\Gamma$, that is the set of ordered pairs of adjacent vertices, and on the set of vertices.

The complete graph $K_n$, for $n\geq 4$ is 2-arc-transitive. However, it is not 3-arc-transitive as it contains two types of 3-arcs: those whose first vertex is equal to its last those and those for which the first vertex is distinct from the last vertex. A cycle is s-arc-transitive for all s.

The study of s-arc-transitive graphs was begun by Tutte [5,6], who showed that for cubic graphs (that is those of valency 3), we have $s\leq 5$. This bound is met by the Tutte-Coxeter graph which is the point-line incidence graph of the generalised quadrangle $W(3,2)$. With the aid of the classification of 2-transitive groups and hence using the classification of finite simple groups, Weiss[7] proved that for graphs with valency at least 3, we have $s\leq 7$. The bound is met by the point-line incidence graphs of the classical generalised hexagons associated with the groups $G_2(q)$.

Praeger[4] initiated a global approach to the study of 2-arc-transitive graphs. Given a graph $\Gamma$ and a partition $\mathcal{B}$ of the vertex set, we can form the quotient graph, denoted $\Gamma_{\mathcal{B}}$, which has vertices the parts of the partition $\mathcal{B}$ and two parts $B_1,B_2$ are adjacent if there exists $v\in B_1$ and $w \in B_2$ such that v is adjacent to w in the original graph. We say that $\Gamma$ is a cover of $\Gamma_{\mathcal{B}}$ if whenever two blocks are adjacent in the quotient graph, the graph induced by $\Gamma$ between the two blocks is a complete matching.

Now if $\mathcal{B}$ is preserved by $\mathrm{Aut}(\Gamma)$ then $\mathrm{Aut}(\Gamma)$ induces automorphisms of $\Gamma_{\mathcal{B}}$. However, if $\Gamma$ is s-arc-transitive then $\Gamma_{\mathcal{B}}$ may not be. Indeed, Babai [1] showed that every regular graph has a cover which is 2-arc-transitive.

This difficulty can be resolved by taking $\mathcal{B}$ to be the orbits of some normal subgroup N of a group G of automorphisms. In this case we denote the quotient by $\Gamma_N$ and refer to is as a normal quotient. If G acts transitvely on the set of s-arcs of $\Gamma$ we refer to $\Gamma$ as being $(G,s)$-arc-transitive. Praeger showed that if $\Gamma$ is $(G,s)$-arc-transitive and N is a normal subgroup of G with at least three orbits on vertices then $\Gamma_N$ is $(G/N,s)$-arc-transitive and $\Gamma$ is a cover of $\Gamma_N$.

This gives a program for studying s-arc-transitive graphs: first study those which are “basic”, that is,  have no proper normal quotients and then study the covers of these basic graphs. There are two types of basic $(G,s)$-arc transitive graphs: those for which every nontrivial normal subgroups of G is transitive on vertices, and those for which every nontrivial normal subgroup has at most two orbits on vertices and there is a normal subgroup with two orbits. Permutation groups with the first property are call quasiprimitive while those of the second kind are called biquasiprimitive.

Quasiprimitive groups are characterised via a version of the O’Nan-Scott Theorem (see this earlier post). In fact, it was this appplication which motivated Cheryl to come up with the characterisation. This divides quasiprimitive groups into 8 types. Cheryl [4] showed that only four of these give rise to examples of 2-arc-transitive graphs.

The biquasiprimitive case is what occurs when our graphs are bipartite. If $\Gamma$ is bipartite, then a vertex-transitive group G of automorphisms will have an index two subgroup $G^+$ which fixes each of the two parts of the bipartition. This subgroup is normal and vertex-intransitive so we cannot hope to have a quasiprimitive group of automorphisms. Hence biquasiprimitive groups are the basic case here. Cheryl Praeger has explored the structure of biquasiprimitive groups [3] . For a biquasiprimitive group G, the group $G^+$ may or may not be quasiprimitive on each of its two orbits. However, up until now we have not known of any examples of 2-arc-transitive graphs for which G is biquasiprimitive on vertices but $G^+$ is not quasiprimitive on its two orbits. Our paper provides the first such family of graphs.

The story does not end here though. Given a bipartite $(G,s)$-arc transitive graph, the group $G^+$ contains all vertex stabilisers and so $(G^+)_v=G_v$ for all vertices v. In particular, $(G^+)_v$ acts transitively on the set of s-arcs starting at v. We call a graph $\Gamma$ locally $(G,s)$-arc transitive if for each vertex v, $G_v$ acts transitively on the set of s-arcs starting at v. If G does not act transitively on vertices then $\Gamma$ will be $(G,s)$-arc transitive. However, if G does not act transitively on vertices then $\Gamma$ is bipartite and the two bipartite halves will be orbits of G. Note that in this case the graph may not be regular. Stellmacher has an unpublished proof that for a locally $(G,s)$-arc transitive graph with each vertex having valency at least 3, we have $s\leq 9$. This bound is met by the point-line incidence graph of the classical generalised octagons associated with the groups ${}^2F_4(q)$ with $q=2^n$. The vertices corresponding to points have valency $2^n+1$ while the vertices corresponding to the lines have valency $2^{2n}+1$.

I studied locally s-arc-transitive graphs with Cai Heng Li and Cheryl Praeger [2] and we showed that the same quotienting process forms a good method for their study. In particular, given a locally $(G,s)$-arc transitive graph $\Gamma$ such that G is not transitive on vertices, if G has a nontrivial normal subgroup which is intransitive on each of the two bipartite halves then the quotient graph $\Gamma_N$ is locally $(G/N,s)$-arc transitive and $\Gamma$ is a cover of $\Gamma_N$. Thus the basic graphs are those for which G is quasiprimitive on at least one of the two bipartite halves. Note that the actions of G on its two orbits are not necessarily equivalent, so it is possible for G to be quasiprimitive on one orbit and not quasiprimitive on the other. In this case, if we take a normal subgroup N which is transitive on one G-orbit and intransitive on the other, the quotient graph $\Gamma_N$ is a star.

Now this also suggests an alternative way to study bipartite s-arc-transitive graphs. Given a $(G,s)$-arc transitive graph $\Gamma$ which is bipartite, we can take a normal subgroup N which is maximal subject to having at least three orbits on vertices. Then $\Gamma_N$ is a $(\overline{G},s)$-arc transitive graph where $\overline{G}=G/N$ and $\overline{G}$ is biquasiprimitive on vertices. Now $\Gamma_N$ is locally $(\overline{G},s)$-arc transitive. If $\overline{G}$ is not quasiprimitive on each of its two orbits on vertices then we can still take a normal quotient of $\Gamma_N$ and get a smaller graph with is locally s-arc-transitive. So for  each graph in our new family of $(G,2)$-arc-transitive graphs given in the paper, since G is biquasiprimitive on vertices but $G^+$ is not quasiprimitive on each of its two orbits, we can still find a smaller locally 2-arc-transitive graph covered by our original graph.

References

[1] L. Babai, Arc transitive covering digraphs and their eigenvalues. J. Graph Theory 9 (1985), 363–370.

[2] Michael Giudici, Cai Heng Li and Cheryl E. Praeger, Analysing nite locally s-arc transitive
graphs, Trans. Amer. Math. Soc. 356 (2004), 291-317.

[3] Cheryl E. Praeger, Finite transitive permutation groups and bipartite vertex-
transitive graphs, Illinois J. Math. 47(1) (2003), 461-475.

[4] Cheryl E. Praeger, An O’Nan-Scott theorem for nite quasiprimitive permutation
groups and an application to 2-arc transitive graphs. J. London Math. Soc. (2)
47 (1993), 227-239.

[5] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43
(1947) 459-474.

[6] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959)
621-624.

[7]  Richard Weiss, The nonexistence of 8-transitive graphs, Combinatorica 1 (1981),
309-311