This file is a repository of research snapshots that have previously appeared on my web page.
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 g∈G 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 J. Araújo, P. J. Cameron and W. Bentz, The existential transversal property: a generalization of homogeneity and its impact on semigroups, Trans. Amer. Math. Soc. 374 (2021), 1155-1195; doi: 10.1090/tran/8285.
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 R. A. Bailey, P. J. Cameron, L. H. Soicher and E. R. Williams, Substitutes for the non-existent square lattice designs for 36 varieties, J. Agricultural, Biological and Environmental Statistics 25 (2020), 487-499; doi: 10.1007/s13253-020-00388-1.
There are various graphs defined on the set of elements of a group, such as
There are many questions about this sequence of graphs: for example, when are consecutive graphs equal? connectedness, clique number, independence number, chromatic number, and so on. 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 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.
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.
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.
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 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.
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….
A new update: Veronica Phan and I showed that the chromatic number of the enhanced power graph is equal to its clique number, and is equal to the maximum order of an element of the group.
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.
At present I have a number of ongoing research projects on graphs defined on algebraic structures, mostly with colleagues in India.
For which groups is the power graph a cograph? The power graph of a group G has vertex set G and an edge from x to y if one is a power of the other. A cograph is a graph with no induced 4-vertex path. This question generalises the classification of groups in which every element has prime power order, first posed by Graham Higman in the 1950s. With Pallabi Manna and Ranjit Mehatari, I have made some progress on this. The class of groups in question is subgroup-closed; we have determined the nilpotent groups and the simple groups in the class, and have a partial description of the soluble groups.
Super graphs For various classes of graphs defined on groups, and various natural partitions on groups, such as "conjugacy" or "same order", one can define a graph in which x and y are joined if some elements in their equivalence classes are joined in the original graph. We (G. Arunkumar, Rajat Kanti Nath and Lavanya Selvaganesh) call these names on the pattern "conjugacy superpower graphs". Among a variety of results, we have shown that the conjugacy supercommuting graph coincides with the commuting graph if and only if the group is 2-Engel, that is, satisfies the identity [[y,x],x] = 1; while the groups for which the conjugacy superpower graph is equal to the power graph are just the Dedekind groups (those with all subgroups normal).
Commuting graphs Which pairs of groups have isomorphic commuting graphs? With Vikraman Arvind, I have examined this question. If two groups of the same order are isoclinic, then their commuting graphs are isomorphic. The converse is false, but we think it may be true for nilpotent groups of class 2; we can prove this in some cases.
Universality of zero divisor graphs of rings Rings here are finite commutative with identity; the zero divisor graph has vertices the zero divisors, two vertices joined if their product is 0. We (G. Arunkumar, T. Tamizh Chelvam abd T. Kavaskar) have shown that, for various classes of rings, the zero divisor graphs are universal, that is, contain every finite graph as an induced subgraph. There are some interesting classes where this is not true, for example, local rings whose maximal ideal is principal: the zero divisor graph is a threshold graph (and is universal for such graphs).
Other work I already mentioned the work with Swathi V. V. and M. S. Sunita on matchings: one of our striking results is that the matching numbers of the power graph and enhanced power graph of a finite group are equal, even though we cannot say what the value is in all cases. Also, with R. Raveendra Prathap and T. Tamizh Chelvam, we have generalised the prime sum graph of a finite abelian group to the "subgroup sum graph", and investigated its properties.
With Marina Anagnostopoulou-Merkouri and Enoch Suleiman, I defined a concept for finite permutation groups lying between transitivity and primitivity, which we called "pre-primitivity". It has the property that it is logically independent of quasiprimitivity, but together with quasiprimitivity it is equivalent to primitivity. So it throws some light on the gap (which confused Galois, who devised both concepts) between quasiprimitivity and primitivity. We proved various things about pre-primitivity. The paper is here.
In subsequent work with Marina, I have defined an even weaker concept, which we don't have a name for yet, tentatively the OBS property. The term comes from experimental design in statistics, where an orthogonal block structure is a set of partitions of a finite set which forms a lattice (with top element the partition with a single part and bottom element the partition into singletons), such that any partition in the set is uniform, and any two commute (as relations). A transitive permutation group has the OBS property if the partitions invariant under the group form an orthogonal block structure. This property lies between transitivity and pre-primitivity, and almost all transitive groups appear to satisfy it. This is still under investigation.
A base for a permutation group is a sequence (a1,…,ar) of points in the permutation domain whose pointwise stabiliser is the identity. A base is irredundant if no point in the base is fixed by the stabiliser of its predecessors; it is minimal if no point in the base is fixed by the stabiliser of all the others.
A couple of things are clear:
In 1995, Dima Fon-Der-Flaass and I showed that the three conditions on irredundant bases, namely
Recently several people (Murray Whyte, Scott Harper, Pablo Spiga, maybe others) asked whether the set of sizes of irredundant bases form an interval. This is true. However, the analogue for minimal bases is false. For any integer d > 1, there is a group whose minimal bases have sizes 1 and d only. However, it is not yet known whether they do form an interval if the permutation group is required to be transitive.
A further question is: What happens for greedy bases? One of these is found by choosing the next base point in an orbit of maximum size for the stabiliser of its predecessors. (There is some variability because there might be a number of orbits of the same size.)
Peter J. Cameron
4 March 2024