Perth, week 4

And now the time in Adelaide and Perth is over. We are back in London, having arrived on the same day as we left Australia. This was the first time I have done this, and I really don’t recommend it. Being awake for 28 hours, after just 5 hours sleep, is quite an ordeal. And it was not a trouble-free flight. The plane had a mechanical fault, and had to return to the gate for an engineer. This cost us an hour, and meant we missed our connection in Dubai, my least favourite of all large airports, and certainly not one where it is possible to make a tight connection. Then there was a 15 minute delay landing at Heathrow, and I was in the immigration hall for 45 minutes – don’t get me started on that!

This week, Rosemary gave a colloquium talk on “Design of dose-escalation trials: Research spurred by a trial that went wrong”, and a seminar to the agricultural statisticians at DAFWA on optimality for designs with low replication.

One of the problems I posed at the problem session asked for a bijection between two apparently unrelated sets. Gordon Royle found a paper by Ossona de Mendez and Rosenstiehl from 2004 which didn’t quite solve this but did something rather similar. So I was provoked to pose a more general problem. Here it is. It may be that the experts on hypermaps know something about this …

Let f(n,t) be the number of t-tuples of permutations in the symmetric group Sn which generate a transitive subgroup. Then f(n,t) is divisible by (n−1)!. For the symmetric group acts by conjugation on the set of such tuples; the stabiliser of any tuple is the centraliser of the (transitive) group it generates, and hence is semiregular, and has order dividing n; so the size of any orbit is a multiple of (n−1)!.

Accordingly, let f(n,t) = (n−1)!g(n,t).

Problem: Do the numbers g(n,t) count anything interesting?

It is known that g(n,1) = 1, while g(n,2) is the number of connected (or indecomposable) permutations of {1,…,n+1} (these are permutations for which there does not exist k between 1 and n inclusive such that the permutation maps {1,…,k} to itself). The sequence counting connected permutations has the property that the ordinary generating function of its negative is the inverse of the ordinary generating function of the factorial numbers, even though neither series converges except at the origin.

Meanwhile, John Bamberg and I have been using eigenvalue techniques to decide when the symmetric group Sn, acting on the set of k-subsets, is synchronizing (or separating). This involves finding bounds for clique number and independence number for various unions of graphs in the Johnson association scheme. So it was back to Philippe Delsarte’s thesis for the eigenmatrix of this scheme (involving Eberlein polynomials), and some smart programming by John to implement bounds due to Hoffman and Delsarte. Work proceeds on this, as also on the derangement problem I mentioned in the first of this series. We know now that the quotients of transitive groups by the subgroups generated by derangements are more general than Frobenius complements; there are examples of primitive groups of degree 625 where these quotients are the Klein group or S3, neither of which is a Frobenius complement. So we are left with the nagging question of whether or not every finite group can occur here.

I believe that your numbers $g(n,t)$ count the number of subgroups of index $n$ in a free group of rank $t$. There is a chapter by Liskovets and Mednykh in Formal Power Series and Algebraic Combinatorics (Ed. Krob and Mikhalev, Springer) which discusses this sort of thing.