The fourth day began with a talk by László Babai on his quasi-polynomial algorithm for graph isomorphism. Two longer and more detailed accounts were scheduled for the workshop; this talk gave the context, and an important lemma which underlies the proof.
Then Cheryl Praeger talked about work with Stephen Glasby, Kyle Ross, and Gabriel Verret on the composition length of a primitive permutation group of degree n. Laci Pyber had outlined a c log n bound, but Cheryl and her coauthors have made this precise, finding the best possible constant c (which turns out to be 8/3) and determining the groups which meet this bound. I suggest an exercise for anyone interested: find a good bound for the composition length of a 2-transitive group – this will be much easier! In the discussion, the result that João and I found last year for the number of generators of a 2-transitive group (namely 2) was recalled. I still find it hard to believe that nobody noticed this before!
Francesco Matucci told us about hyperbolic groups (those for which a Cayley graph is δ-hyperbolic in the sense of Gromov), and presented a theorem which has as a corollary that torsion-free hyperbolic groups embed in the rational group (the group of maps of Cantor space generated by transducers acting on infinite strings).
Dugald Macpherson came next. He and his colleagues have been investigating very wide model-theoretic generalisations of the Hasse–Weil estimates for definable sets over finite fields. Depending on whether the approximations are exact or approximate, very different results are obtained.
Michael Giudici and his colleagues have been investigating semiprimitive permutation groups, those in which every non-trivial normal subgroup is either transitive or semiregular. This condition is very relevant to things related to the Weiss conjecture, which Pablo Spiga discussed. The role of minimal normal subgroups and the socle is taken by plinths for such a group (minimal transitive normal subgroups); remarkably, they have good control over these.
Ben Steinberg’s talk was about random walks on a module M over a finite ring R, where the transitions are affine maps of the form x → ax+b. Here, a is not required to be a unit, so the maps may be non-invertible. For example, if R is the 2-element field, the steps are random translations or jumps to random points. He uses the representation theory of semigroups (the subject of his recent book) to work out the eigenvalues of the transition matrix.
Wolfram Bentz told us about permutation groups, transformation semigroups, and graphs; at least this was material which I knew about, although there were probably others who didn’t.
Misha Volkov gave a very nice talk about completely reachable automata, those for which every non-empty subset of the states is the image of some composition of transitions. Clearly the semigroup generated by such an automaton has size at least 2n−1, where n is the number of states. This is a much stronger condition than synchronization, and Misha was able to use binary trees to construct and characterise such automata.
The day, and the conference proper, ended with my talk; you can find the slides in the usual place.
Peter Cameron's Blog 