Old research snapshots

This file is a repository of research snapshots that have previously appeared on my web page.

The existential transversal property

The permutation group G has the k-existential transversal property, or k-et for short, if there is a k-subset A of the domain (the witnessing set) such that, for any k-partition P of the domain, there exists gG such that Ag is a transversal to P. With João Araújo and Wolfram Bentz, I determined all the finite permutation groups of degree n with the k-et property for 4 ≤ k ≤ n/2, apart from a few exceptional cases with k = 4 or k = 5. There are applications to regular semigroups. See arXiv 1808.06085.

Sylvester designs

The Sylvester graph is a remarkable distance-transitive graph of valency 5 on 36 vertices, which can be constructed using the even more remarkable outer automorphism of the symmetric group S6, as shown by Sylvester (and described in Chapter 6 of my book with Jack van Lint). Now there is no affine plane of order 6; but, with Rosemary Bailey, Leonard Soicher and Emlyn Williams, I have been investigating block designs for which there is a Sylvester graph on the set of treatments, and the concurrences are 2 for edges of the graph and 1 for all other pairs. They, and designs obtained by deleting resolution classes, are good substitutes for the missing lattice designs. There seem to be many such designs; but just one admits all the symmetries of the Sylvester graph. See arXiv 1912.08087.

Commuting graph, power graph, etc.

There are various graphs defined on the set of elements of a group, such as

For any group, the power graph is a subgraph of the enhanced power graph, which is a subgraph of the commuting graph; and, if the group is non-abelian and 2-generated, the commuting graph is a subgraph of the non-generating graph.

There are many questions about this sequence of graphs: for example, when are consecutive graphs equal (solved, see here for the first two pairs); connectedness, clique number, independence number, chromatic number, and so on (see arXiv 1910.06721). One interesting observation is that a random walk on the commuting graph has limiting distribution which is uniform on conjugacy classes: what about random walks on the other graphs?

Diagonal groups

Diagonal groups are one class of primitive permutation groups arising in the O'Nan–Scott theorem, and are slightly mysterious. With Rosemary Bailey, Cheryl Praeger and Csaba Schneider, I am working on understanding these groups better. As spin-offs, I have shown (with John Bray, Qi Cai, Pablo Spiga and Hua Zhang), using the Hall–Paige conjecture, that diagonal groups with at least three simple factors in the socle are non-synchronizing, and (with Sean Eberhard) that they preserve non-trivial association schemes.

Integrable groups

With João Araújo, Carlo Casolo and Francesco Matucci, I determined the set of natural numbers n with the property that every group of order n is the derived subgroup of some group. This set is closely related to (but slightly larger than) the set of n for which every group of order n is abelian. We also showed that if a finite group is a derived group, then it is the derived group of a finite group.

Equitable partitions of Latin square graphs

With Rosemary Bailey, Alexander Gavrilyuk, and Sergey Goryainov, I determined the equitable partitions of Latin square graphs under an extra assumption on eigenvalues. A partition is equitable if, given any two parts, the number of neighbours in the second part of a vertex in the first depends only on the parts and not on the chosen vertex.

Power graphs of torsion-free groups

In the directed power graph of a group, there is an arc from x to y if y is a power of x; for the undirected power graph, just ignore directions. The power graph does not in general determine the directed power graph, even up to isomorphism (though it does for finite groups). With Horacio Guerra and Šimon Jurina, I showed that for various torsion-free groups, the directions are indeed determined.

Diagonal groups (update)

Diagonal groups D(G,m) for G a finite simple group are one of the classes arising in the O'Nan--Scott Theorem. However, they can be defined for any group G, not necessarily finite or simple. With Rosemary Bailey, Cheryl Praeger and Csaba Schneider, I have defined for each pair G,m where G is a group and m a dimension greater than 1, a geometric structure called a diagonal semilattice whose automorphism group is the corresponding diagonal group. We also gave simple axioms for these geometries. For m = 2, a structure satisfying the axioms is precisely a Latin square, but for m > 2 the group G arises naturally from the combinatorial axioms.

These structures consist of m+1 partitions of a set, any m of which are the least elements in a Cartesian lattice. With Rosemary, Cheryl, and Michael Kinyon, I have looked at larger sets of partitions satisfying these conditions, and found connections with orthogonal arrays, arcs in projective space, and MDS codes.

Finally, the paper with Sean Eberhard contains a mistake which we have been unable to fix.

Power graphs (update)

There are various classes of graphs which are recognised by a small list of forbidden induced subgraphs, and which have nice algorithmic properties and various applications; these include perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs. With Pallabi Manna and Ranjit Mehatari, I have investigated when the power graph of a group belongs to one of these classes. Power graphs are always perfect; we have found all groups for which they are either split or threshold, and all nilpotent groups for which they are either cographs or chordal. In addition, there is a long survey article on power graphs. One curious fact proved here is that, if f(n) is the clique number of the power graph of a cyclic group of order n, then φ(n) ≤ f(n) ≤ cφ(n), where φ is Euler's totient function and c = 2.6481017597….

Automorphisms of shift spaces

In two papers with Collin Bleak and Shayo Olukoya, I have looked further at the connection between strongly synchronizing automata and transducers, the Higman–Thompson finitely presented infinite simple groups, and the automorphism group of the one- or two-sided shift.

Peter J. Cameron
3 November 2021