Skip to content

A new family of 2-arc-transitive graphs

December 22, 2009

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

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: