papers – SymOmega

Symmetries of Graphs and Networks IV

Last week I was at the Symmetries of Graphs and Networks IV conference at Rogla in Slovenia. The conference webpage is here. At the same time was the annual PhD summer school in discrete maths. As usual it was a very enjoyable and well organised conference. It was good to catch up with some of the regulars and meet a few new people as well

I was one of the invited speakers and spoke about some of the work that I have been doing recently with Luke Morgan on graph-restrictive permutation groups. The slides are available here. The two relevant preprints are on the arxiv here and here.

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.

Transitive projective planes

A little while ago, Gordon wrote about a conjecture about projective planes whose automorphism group acts transitively on points. It is thought that the Desarguesian planes are the only examples.

The best results on groups acting on projective planes in the last five years are due solely to Nick Gill, and he has recently posted a preprint to the arxiv containing an astonishing result. Gill’s work seems to have not gained the profile it deserves and so we want to make special mention of his main theorems (n.b., $O(G)$ is the largest odd-order normal subgroup of $G$ ):

Theorem A: Suppose that a group $G$ acts transitively on the set of points of a finite non-Desarguesian projective plane. Then the rank of the largest elementary-abelian 2-subgroup of $G$ is at most $1$ .

Theorem B: Suppose that a group $G$ acts transitively on the set of points of a non-Desarguesian projective plane. Then we have the following possibilities:

$G$ has a normal 2-complement (and so $G$ is soluble).
$G/O(G)$ is isomorphic to $SL_2(3)$ or to a non-split degree 2 extension
of $SL_2(3)$ (and so $G$ is soluble).
$G = O(G) : SL_2(5)$ or $G = (O(G) : (SL_2(5)).2$

So to summarise, if a group $G$ acts transitively on a finite non-Desarguesian projective plane, then the Sylow 2-subgroups of G are cyclic or generalized quaternion, and if $G$ is insoluble, then $G/O(G)$ is isomorphic to $SL_2(5)$ or $SL_2(5).2$ .

Well done Nick!

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”

Some interesting open problems on hemisystems

Gordon, Michael and I have just submitted our second paper together, this time we produce examples of hemisystems in small flock generalised quadrangles. So what are these things anyway? Generalised quadrangles have been discussed in depth in Michael’s posts (see this), and in particular, there is an exposition there on GQs arising from BLT-sets/flocks/q-clans. Theses are the only known GQs with parameters $(q^2,q)$ where $q$ is odd. A hemisystem of a generalised quadrangle of order $(s,t)$ is a set $\mathcal{H}$ of half of the lines such that every point is on $(t+1)/2$ lines of $\mathcal{H}$ . These objects are curious in that they give rise to partial quadrangles, Q-antipodal cometric association schemes and strongly regular graphs. We have already written an earlier post containing some of the history of the subject, but to summarise, it was thought for forty years that Segre’s unique example of $H(3,3^2)$ was the only example, Cossidente and Penttila (2005) showed there were infinitely many in the classical GQ $H(3,q^2)$ , and then we showed (2010) that every flock GQ has a hemisystem. Apart from these examples, we find some interesting examples in flock GQs of order $(q^2,q)$ where $q\le 11$ .

One of the main results of our paper is that we have classified the hemisystems of flock GQs of order $(25,5)$ :

hemisystems:
- Cossidente-Penttila hemisystem
- $3.A7$ -hemisystem
Fisher-Thas-Walker-Kantor-Betten(5) hemisystems:
- a hemisystem found by Bamberg, De Clerck and Durante
- two new ones (stabilisers $5^2:(4\times S_3)$ and $S_3$ ).

Along the way, we came upon some interesting problems that are still open…

Continue reading “Some interesting open problems on hemisystems”

Quotients of geometries

Last week I uploaded to the arxiv the latest in a sequence of papers that introduces a “normal quotient” method for the study of incidence geometries. The first paper was `Quotients of incidence geometries‘ with Philippe Cara, Alice Devillers and Cheryl Praeger, the second was `Basic and degenerate geometries‘ with Cai Heng Li, Geoffrey Pearce and Cheryl Praeger, and the third was `Basic coset geometries‘ with Geoffrey and Cheryl. I will give a brief outline of the whole project here including motivation and some of the main results.

The study of graphs via their quotients has proved a very fruitful avenue of investigation. The general method for studying a particular class of graphs is to identify some reduction process that takes any graph in the family to a “basic graph” in the family, determine all “basic graphs”, and then determine all ways of lifting the “basic graphs” so that we can enumerate all graphs in the class. Examples of classes of graphs where this has proved a useful method of attack are:

distance-transitive graphs: Distance-transitive graphs with an imprimitive group of automorphisms are either bipartite or antipodal and can be reduced to smaller distance-transitive graph. Hence the basic graphs are the ones with a primitive group of automorphisms.
${s}$ -arc transitive graphs: If ${G}$ acts transitively on the set of ${s}$ -arcs, for ${s\geq 2}$ of a graph ${\Gamma}$ and ${G}$ has a normal subgroup ${N}$ with at least 3 orbits on vertices then the quotient graph ${\Gamma_N}$ is also ${s}$ -arc transitive and ${\Gamma}$ is cover of ${\Gamma_N}$ . Hence the basic graphs to study are those for which every nontrivial normal subgroup of ${\mathrm{Aut}(\Gamma)}$ has at most two orbits, that is, ${\mathrm{Aut}(\Gamma)}$ is quasiprimitive (all nontrivial normal subgroups are transitive) or biquasiprimitive (all have at most 2 orbits but not all are transitive).
vertex-intransitive, locally ${s}$ -arc transitive graphs: Here the graphs are bipartite and the bipartite halves are the two orbits of ${G}$ on vertices. We can apply the same quotienting process and the basic graphs are those for which ${G}$ is quasiprimitive on at least one orbit.

In all cases we can use the O’Nan-Scott Theorem for primitive or quasiprimitive groups to study the basic graphs. This involves seeing which primitive/quasiprimitive types are possible and then determining all graphs for a given type. Usually we can reduce to studying the case where the action is either almost simple or affine.

The aim of our project on incidence geometries is to extend these methods to geometries. Jacques Tits introduced the notion of a building to study the simple groups of Lie type. Francis Buekenhout then introduced incidence geometries and their associated diagrams as a generalisation in an attempt to find a larger class of geometries that would include buildings but also contain geometries associated to the sporadic simple groups. One rationale for our project was to give a geometrical justification for the study of geometries of simple groups. The hope was that geometries of almost simple groups would arise as one of a small number of “basic” families of graphs.

First some definitions. A pregeometry ${\Gamma = (X,\ast,t)}$ consists of a set ${X}$ of elements (often called points) with an incidence relation ${\ast}$ on the points, and a map ${t}$ from ${X}$ onto a set ${I}$ of types. The incidence relation is symmetric and reflexive, and if ${x \ast y}$ we say that ${x}$ and ${y}$ are incident. Furthermore if ${x \ast y}$ with ${x \neq y}$ then ${t(x) \neq t(y)}$ . The number ${|I|}$ of types is called the rank of the pregeometry. A rank 2 geometry is merely a bipartite graph and so our earlier work on quotients of locally ${s}$ -arc transitive graphs can be seen as investigating the rank 2 case.

A flag ${F}$ is a set of pairwise incident elements of ${\Gamma}$ (which implies that the elements of ${F}$ are of pairwise distinct types). The type of a flag is the set of types of its elements. A chamber is a flag containing one element of each type. A pregeometry in which every flag is contained in a chamber is called a geometry. The typical example is a projective space. Here the elements are the points, lines, planes etc and incidence is given by inclusion.

Let ${\Gamma=(X,*,t)}$ be a pregeometry and let ${\mathcal{B}}$ be a partition of ${X}$ which is a refinement of the type partition of ${\Gamma}$ . We define a new pregeometry ${\Gamma_{/\mathcal{B}}=(\mathcal{B},*_{/\mathcal{B}},t_{/\mathcal{B}})}$ where

${B_1 *_{/\mathcal{B}} B_2}$ if and only if there exist ${\alpha_i\in B_i}$ (for ${i=1,2}$ ) with ${\alpha_1*\alpha_2}$ ,
${t_{/\mathcal{B}}:X_{\mathcal{B}}\rightarrow I}$ and ${t_{/\mathcal{B}}(B)=t(\alpha)}$ for ${\alpha\in B}$ .

Quotients of geometries under certain conditions were studied by Tits and Pasini. However, in general the quotient of a geometry is not necessarily a geometry. Our first paper investigated necessary and sufficient conditions for when the quotient of a geometry is a geometry, and also which geometrical properties are preserved by quotients.

The automorphism group of a pregeometry is the group of all permutations of the element set ${X}$ that preserves the type of each element and that preserves incidence. We say that a group of automorphisms ${G}$ is vertex-transitive on the pregeometry if ${G}$ is transitive on each set ${X_i=t^{-1}(i)}$ for ${i\in I}$ , that is, is transitive on each set of points of a given type. That is, the orbits of ${G}$ on points are as large as possible. We say that ${G}$ is incidence-transitive if for each pair ${\{i,j\}}$ of types, ${G}$ is transitive on the set of flags of type ${\{i,j\}}$ . We say that ${G}$ is flag-transitive if for each ${J\subseteq I}$ , ${G}$ is transitive on the set of flags of type ${J}$ .

One class of pregeometries are coset pregeometries. Given a group ${G}$ with subgroups ${\{G_i\}_{i\in I}}$ , the coset pregeometry ${\Gamma=\Gamma(G,\{G_i\}_{i\in I})}$ is the pregeometry whose elements of type ${i\in I}$ are the right cosets of ${G_i}$ in ${G}$ and two cosets ${G_ix}$ and ${G_jy}$ are incident if ${i\neq j}$ and ${G_ix\cap G_jy}$ is nonempty. The group ${G}$ acts by right multiplication on the elements of ${\Gamma}$ inducing automorphisms of the pregeometry, that is, maps incident elements to incident elements. In our first paper we showed that a pregeometry is a coset pregeometry if and only if its group of automorphisms is incidence-transitive and vertex-transitive and the pregeometry contains a chamber.

One of the main results of our first paper is that the quotient of a coset pregeometry is still a coset pregeometry. This motivated us to take the class of coset pregeometries with connected rank 2 truncations as the class of objects that we should study, instead of the narrower class of flag-transitive geometries.

The next thing to do is to determine what the degenerate and basic coset pregeometries should be. The basic pregeometries are those such that all quotients are degenerate. We investigated this question in our second paper. The definitions will depend on whether we are taking normal quotients (that is quotients with respect to the set of orbits of some normal subgroup) or imprimitive quotients, (that is quotients with respect to some ${G}$ -invariant partition). In the normal quotients case we were able to show that the basic pregeometries can be built from pregeometries where for each type ${i}$ , the action of ${G}$ is quasiprimitive on each set of elements of type ${i}$ . In the imprimitive quotients case we replace `quasiprimitive’ with `primitive’.

Thus the important pregeometries to study are those where ${G}$ is quasiprimitive on each set of elements of type ${i}$ . We investigated these in our third paper which contains many constructions of flag-transitive geometries. One type of primitive action is the almost simple case. The projective space ${PG(n,q)}$ is an example of an incidence geometry of rank ${n}$ and the automorphism group ${P\Gamma L(n+1,q)}$ is primitive of almost simple type on each set of elements. Our initial aim was to see if there was some number ${N}$ such that if ${\Gamma}$ were a flag-transitive geometry of rank at least ${N}$ such that the automorphism group ${G}$ acts primitively on each set of elements then ${G}$ is almost simple. However, the main result of our third paper was to show that this is not true. In fact for each positive integer ${n}$ and each of the 8 O’Nan-Scott types of primitive group, we were able to find a primitive group ${G}$ on a set ${\Omega}$ whose action is primitive of that type and construct a rank ${n}$ geometry ${\Gamma}$ such that each set of elements of a given type is a copy of ${\Omega}$ and ${G}$ acts on flag-transitively on ${\Gamma}$ .

Point regular automorphism groups of generalised quadrangles

John and I have just uploaded to the arxiv a copy of our recent paper, `Point regular automorphism groups of generalised quadrangles‘. We investigate the regular subgroups of some of the known generalised quadrangles. We demonstrate that the class of groups which can act as a point regular group of automorphisms of a generalised quadrangle is much wilder than previously thought.

A permutation group ${G}$ on a set ${\Omega}$ acts regularly on a set ${\Omega}$ if it acts transitively on ${\Omega}$ and only the identity of ${G}$ fixes an element of ${\Omega}$ . Studying regular automorphism groups of projective planes has received much attention over the years. Recently attention has turned to the study of groups acting regularly on generalised quadrangles.

Dina Ghinelli proved in 1992 that a Frobenius group or a group with a nontrivial centre cannot act regularly on the points of a generalised quadrangle of order ${(s,s)}$ , where ${s}$ is even. Stefaan De Winter and Koen Thas proved in 2006 that if a finite thick generalised quadrangle admits an abelian group of automorphisms acting regularly on its points, then it is the Payne derivation of a translation generalised quadrangle of even order. Satoshi Yoshiara proved that there are no generalised quadrangles of order ${(s^2 , s)}$ admitting an automorphism group acting regularly on points.

Continue reading “Point regular automorphism groups of generalised quadrangles”

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”

Commuting graphs of groups

Over the summer I have had the pleasure of supervising a vacation student Aedan Pope. This is a program funded by the Australian Mathematical Sciences Institute which allows maths students to spend 6 weeks working on a project in the summer vacation (usually after third year) and also funds a trip to Sydney for the student to go to the CSIRO‘s Big Day In.

Aedan Pope’s research project focussed on commuting graphs of groups and we have just submitted a paper with the results. It is available on the arxiv. I will outline the work here.

Given a group G, the commuting graph of G is the graph whose vertices are the elements of G which do not lie in the centre of G and two vertices are adjacent if they commute. The commuting graph of a group appears to have first been studied in Brauer and Fowler’s paper `On groups of even order‘. Though they don’t actually use the words “commuting graph” they do study the distance between two elements of the group in what would be the commuting graph.

My interest in commuting graphs was piqued by the paper `On the commuting graph associated with the symmetric and alternating groups‘ by Iranmanesh and Jafarzadeh. This paper shows that when the commuting graph of the alternating group is connected it has diameter at most 5. They also make the following conjecture:

There is an absolute constant c such that if the commuting graph of a finite group is connected, it has diameter at most c.

Continue reading “Commuting graphs of 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)$ .