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 of vertices such that is adjacent to but , that is, it is a path in the graph which cannot immediately go back upon itself. A graph is called* s-arc-transitive* if acts transitively on the set of s-arcs in . 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 is *s*-arc-transitive then it is also *(s-1)*-arc-transitive. In particular, acts transitively on the set of arcs of , that is the set of ordered pairs of adjacent vertices, and on the set of vertices.

The complete graph , for 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 . This bound is met by the Tutte-Coxeter graph which is the point-line incidence graph of the generalised quadrangle . 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 . The bound is met by the point-line incidence graphs of the classical generalised hexagons associated with the groups .

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

Now if is preserved by then induces automorphisms of . However, if is *s*-arc-transitive then 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 to be the orbits of some normal subgroup *N *of a group *G *of automorphisms. In this case we denote the quotient by and refer to is as a normal quotient. If *G *acts transitvely on the set of s-arcs of we refer to as being -arc-transitive. Praeger showed that if is -arc-transitive and *N *is a normal subgroup of *G *with at least three orbits on vertices then is -arc-transitive and is a cover of .

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 -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 is bipartite, then a vertex-transitive group *G *of automorphisms will have an index two subgroup 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 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 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 -arc transitive graph, the group contains all vertex stabilisers and so for all vertices *v*. In particular, acts transitively on the set of *s*-arcs starting at *v*. We call a graph locally -arc transitive if for each vertex *v*, acts transitively on the set of s-arcs starting at *v*. If G does not act transitively on vertices then will be -arc transitive. However, if *G *does not act transitively on vertices then 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 -arc transitive graph with each vertex having valency at least 3, we have . This bound is met by the point-line incidence graph of the classical generalised octagons associated with the groups with . The vertices corresponding to points have valency while the vertices corresponding to the lines have valency .

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 -arc transitive graph 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 is locally -arc transitive and is a cover of . 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 is a star.

Now this also suggests an alternative way to study bipartite *s*-arc-transitive graphs. Given a -arc transitive graph which is bipartite, we can take a normal subgroup N which is maximal subject to having at least three orbits on vertices. Then is a -arc transitive graph where and is biquasiprimitive on vertices. Now is locally -arc transitive. If is not quasiprimitive on each of its two orbits on vertices then we can still take a normal quotient of and get a smaller graph with is locally s-arc-transitive. So for each graph in our new family of -arc-transitive graphs given in the paper, since *G *is biquasiprimitive on vertices but 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

## Leave a Reply