quasiprimitive – SymOmega

Graph symmetry

John claims that he and Gordon are confused by the various adjectives used by us graph symmetry people and how they relate to each other so I have decided to write some posts outlining the main ones and their importance. There is a nice diagram on wikipedia illustrating the relationship between the main ones and I will use that as the basis of my discussion.

Throughout I will use ${\Gamma}$ to denote a graph and ${G}$ to denote a group (unfortunately some authors use the reverse.) All graphs will be simple (that is, undirected, no multiple edges, and no loops) and finite. The full automorphism group of a graph, that is the group of all permutations of the set of vertices that take edges to edges, will be denoted by ${\mathrm{Aut}(\Gamma)}$ . I will use ${V\Gamma}$ to denote the set of vertices, ${E\Gamma}$ to denote the set of edges and ${A\Gamma}$ to denote the set of arcs, that is the set of ordered pairs of adjacent vertices.

The first adjective is regular. A graph is called regular if each vertex has the same number of neighbours. This number is referred to as the valency of the graph.

A graph is called vertex-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of vertices, that is, for all ${v, u\in V\Gamma}$ there exists an automorphism ${g}$ such that ${u^g=v}$ . Sometimes we wish to restrict our attention to a subgroup ${G}$ of ${\mathrm{Aut}(\Gamma)}$ and say that ${\Gamma}$ is ${G}$ -vertex-transitive if ${G}$ acts transitively on ${V\Gamma}$ .

One consequence of a graph being vertex-transitive is that it is regular: if an automorphism ${g}$ maps ${u}$ to ${v}$ then it also maps the neighours of ${u}$ to the nieghbours of ${v}$ . However, not all regular graphs are vertex-transitive. In fact, it is even possible for a regular graph to have a trivial automorphism group, for example, the Frucht graph.

Continue reading “Graph symmetry”

Rank 3 permutation groups

Alice Devillers, Cai Heng Li, Geoff Pearce, Cheryl Praeger and I have just uploaded to the arxiv a preprint of our recently submitted paper `On imprimitive rank 3 permutation groups‘.

A permutation group ${G}$ on a set ${\Omega}$ also acts on the set ${\Omega\times\Omega}$ via ${(\omega_1,\omega_2)^g=(\omega_1^g,\omega_2^g)}$ . If ${G}$ is transitive on ${\Omega}$ then we cannot expect it to be transitive on ${\Omega\times\Omega}$ as the subset ${\{(\omega,\omega)\mid\omega\in\Omega\}}$ is an orbit. The best that we can hope for is that ${G}$ has two orbits on ${\Omega\times\Omega}$ and this is equivalent to ${G}$ acting 2-transitively on ${\Omega}$ , that is, ${G}$ acts transitively on the set of ordered pairs of distinct elements of ${G}$ . The rank of a permutation group ${G}$ is the number of orbits of ${G}$ on ${\Omega\times\Omega}$ . Thus 2-transitive groups have rank 2.

The number of orbits of ${G}$ on ${\Omega\times \Omega}$ is equal to the number of orbits of the point stabiliser ${G_{\omega}}$ on ${\Omega}$ . Indeed, given an orbit ${\Delta}$ of ${G_{\omega}}$ on ${\Omega}$ the set ${\{(\omega,\delta)^g\mid \delta\in\Delta,g\in G\}}$ is an orbit of ${G}$ on ${\Omega\times\Omega}$ . Conversely, given an orbit ${\Delta}$ of ${G}$ on ${\Omega\times\Omega}$ , the set ${\{\delta\in\Omega\mid (\omega,\delta)\in\Delta\}}$ is an orbit of ${G_{\omega}}$ on ${\Omega}$ . In this set up, ${\{\omega\}}$ corresponds to ${\{(\omega,\omega)\mid\omega\in\Omega\}}$ .

Continue reading “Rank 3 permutation groups”

A new family of 2-arc-transitive graphs

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)$ .

Continue reading “A new family of 2-arc-transitive graphs”

The O’Nan-Scott Theorem

I have decided that any mathematical blog entitled SymOmega should have an expository post about one of the most influential theorems of permutation group theory, that is, The O’Nan-Scott Theorem. Originally, this was a theorem about maximal subgroups of the symmetric group. It appeared as an appendix to a paper of Leonard Scott in the proceedings of the Santa Cruz symposium on finite simple groups in 1979, with a footnote that Michael O’Nan had independently proved the same result. Apparently there are even earlier versions due to various people but it was the Classification of Finite Simple Groups (CFSG) which meant that it would become very useful.

In its simplest form the theorem states that a maximal subgroup of the symmetric group $\mathrm{Sym}(\Omega)$ where $|\Omega|=n$ , is one of the following:

$S_k\times S_{n-k}$ , the stabiliser of a k-set (that is, intransitive),
$S_a \mathrm{wr} S_b$ with $n=ab$ , the stabiliser of a partition into b parts of size a (that is, imprimitive), or
primitive (that is, preserves no nontrivial partition) and of one of the following types:

$\mathrm{AGL}(d,p)$ ,

$S_\ell \mathrm{wr} S_k$ with $n=\ell^k$ , the stabiliser of a product structure $\Omega=\Delta^k$ ,

a group of diagonal type, or

an almost simple group.

(These types will be explained in further detail below).

It was soon recognised (perhaps first in a paper of Peter Cameron) that the real power is in the ability to split the finite primitive groups into various types. Problems concerning primitive groups can then be studied by solving them for each type. This often sees questions about primitive groups reduced to questions about simple groups and then the force of the classification can be harnessed to get your result. Furthermore, many results about transitive permutation groups can be reduced to the primitive case and so we actually have a tool for studying questions about transitive groups.

The division of primitive groups into various types is usually finer than given in the statement about maximal subgroups of $S_n$ as we are no longer concerned about maximality in $S_n$ but instead are more concerned about the types of actions. In Cameron’s original paper, the twisted wreath product case (again, more details later) which does not appear as a maximal subgroup of $S_n$ but is an important type of action with a distinctly different flavour to the maximal subgroup $S_\ell \mathrm{wr} S_k$ it is contained in, was left out and this was corrected in a subsequent paper of Aschbacher and Scott, and in work of Laci Kovacs. A complete self-contained proof is given in a paper by Martin Liebeck, Cheryl Praeger and Jan Saxl.

Since I am from Perth, I usually follow the division and labelling into 8 types due to Cheryl Praeger which appears here and here. First we need to deal with a few preliminaries.

Continue reading “The O’Nan-Scott Theorem”