primitive permutation group

Regular cycles of elements in finite primitive permutation groups

Cheryl Praeger, Pablo Spiga and I have just uploaded to the arxiv our preprint Finite primitive permutation groups and regular cycles of their elements. Everyone recalls from their first course in group theory that if you write a permutation in cycle notation, for example (1,2)(3,4,5)(6,7,8,9,10), then its order is the lowest common multiple of it cycle lengths. As I have just demonstrated, not every permutation must have a cycle whose length is the same as the order of the element. We call a cycle of an element g whose length is the order of g, a regular cycle. A natural question to ask is when can you guarantee that a permutation has a regular cycle? Or in particular, for which permutation groups do all elements have a regular cycle?

Clearly, the full symmetric group contains elements with no regular cycles, but what about other groups? Siemons and Zalesskii showed that for any group G between PSL(n,q) and PGL(n,q) other than for (n,q)=(2,2) or (2,3), then in any action of G, every element of G has a regular cycle, except G=PSL(4,2) acting on 8 points. The exceptions are due to isomorphisms with the symmetric or alternating groups. They also later showed that for any finite simple group G,other than the alternating group, that admits a 2-transitive action, in any action of G every element has a regular cycle. This was later extended by Emmett and Zalesskii to any finite simple classical group not isomorphic to PSL(n,q).

With these results in mind, we started investigating elements in primitive permutation groups. The results of this work are in the preprint. First we prove that for $k\leq m/2$ , every element of Sym(m) in its action on k-sets has a regular cycle if and only if m is less than the sum of the first k+1 primes. After further computation we were then willing to make the following conjecture:

Conjecture: Let $G\leqslant Sym(\Omega)$ be primitive such that some element has no regular cycle. Then there exist integers $k\geq1, r\geq1$ and $m\geq5$ such that
G preserves a product structure on $\Omega=\Delta^r$ with $|\Delta|=\binom{m}{k}$ , and $Alt(m)^r \vartriangleleft G\leqslant Sym(m)\textrm{wr} Sym(r)$ , where Sym(m) induces its k-set action on $\Delta$ .

The general philosophy behind why such a result should be true is that most primitive groups are known to be small in terms of a function of the degree. There is a large body of work bounding the orders of primitive permutation groups with the best results due to Maroti. The actions of Sym(m) on k-sets are the usual exceptions.

Our paper goes about attempting to prove this conjecture. We make substantial progress and reduced its proof to having to deal with all the primitive actions of classical groups. Note that Emmett and Zalesskii only dealt with simple ones. One consequence of our work is we showed that every automorphism of a finite simple group has a regular cycle in its action on the simple group.

Pablo and Simon Guest have subsequently gone on to prove the result for all actions of classical groups and so the conjecture is now a theorem.

Pablo gave a great talk about the conjecture and its subsequent proof at the recent BIRS workshop on Permutation Groups in Banff which you can view here.

Derangements

Last week and this week I have been at the University of Southampton visiting Tim Burness to work on our big project concerning derangements. Despite it being summer here, the weather has been more like a Perth winter. I am staying in a self-catered hall of residence so the cooked breakfasts have come to an end and it is back to cornflakes.

A derangement is a permutation that moves all the points of the set which it acts on. I have only recently been converted to the term derangement, have previously preferred the term fixed point free element. Peter Cameron has had a bit to say about derangements in several posts on his blog.

By the Orbit-Counting Lemma, the average number of fixed points of an element of a transitive permutation group is 1. Since the identity permutation fixes all the elements of the set, a transitive permutation group on a set of size at least two must therefore contain a derangement. This leads to the natural questions that have attracted a lot of attention:

how many derangements are there?
what properties do the derangements have?

The project with Tim focuses on the second.

Fein, Kantor and Schacher proved that every transitive permutation group contains a derangement of prime power order. The result was motivated by an application to number theory as the existence of a derangement of prime power order is equivalent to the relative Brauer group of any nontrivial field extension of global fields being infinite. Whereas the existence of a derangement is an elementary observation, the proof of the existence of one of prime power order relies heavily on the Classification of Finite Simple Groups. The proof though does not give information about which primes or which powers.

In fact, not every transitive permutation group contains a derangement of prime order. My favourite example is the Mathieu group $M_{11}$ in its 3-transitive action on 12 points. Note that if a group G acts transitively on a set with the stabiliser of some point being the subgroup H, then an element g fixes a point if and only if it is conjugate to an element of H. Since $M_{11}$ contains a unique conjugacy class of elements of order 2 and a unique class of elements of order 3, and 6 divides the order of the stabiliser of a point ( $PSL(2,11)$ ), it follows that all elements of order 2 and 3 fix a point.

Continue reading “Derangements”

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”

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”

Edge-primitive graphs

I have just finished reading the proofs for my paper `On finite edge-primitive and edge-quasiprimitive graphs’ with Cai Heng Li which has just been accepted in JCTB. This paper has been a long time in the making as Li and I started the work in 2002! Usually when I submit a paper to a journal I put a preprint up on my research web page but I should really start uploading them also to the arxiv so I have just done so and it is now available there.

A graph is called edge-primitive if its automorphism group acts primitively on the set of edges. Many famous graphs such as the Heawood graph, Tutte-Coxeter graph, Hoffman-Singleton graph and Higman-Sims graph are edge-primitive. The paper begins a systematic study of edge-primitive and edge-quasiprimitive graphs by analysing the possible actions on vertices and edges.

Continue reading “Edge-primitive graphs”