Permutation groups in Bristol

On 1 June, a meeting of the “Groups and Applications” triangle was held in Bristol. (This peripatetic meeting was a long thin triangle with vertices London, Birmingham and Manchester, but with the inclusion of Bristol it is not clear what the geometry is.) This meeting was on Permutation Groups, the subject I have worked in since before my birth as a mathematician.

Gareth Tracey spoke about the problem of finding the number of generators of minimal transitive (or primitive) subgroups of the symmetric group of degree n. A transitive group can have as many as n/√log n, but the expectation is that it will have a minimal transitive subgroup with many fewer generators. Gareth gave some very nice results in this direction.

The talk suggested to me a computational problem. Given a transitive group, can we “efficiently” find generators for a minimal transitive subgroup? For example, for an arbitrary subgroup of the symmetric group, Mark Jerrum found an algorithmic proof that it can be generated by at most n−1 elements. If you throw permutations at Jerrum, and allow him to do a polynomial amount of processing on each one (this is the polynomial delay model), he can maintain a set of at most n−1 permutations which generate the same group as all the permutations you have thrown him. The best bound for the number of generators of an arbitrary subgroup is the floor of n/2, due to Annabel McIver and Peter Neumann; I do not know whether such a set can be found with polynomial delay. It might be interesting to see whether Gareth Tracey’s problem can be solved by a polynomial delay algorithm. (Since the number of generators may be exponential, this is the best we can expect.)

I spoke about the road closure problem, due to João Araújo and me. We have a necessary and sufficient condition on a permutation group G for the semigroup of non-units of ⟨G,a⟩ to be idempotent-generated, for all rank 2 maps a. We have a conjecture about which groups satisfy this condition, but no proof yet.

Finally, Barbara Baumeister talked about the following problem: for which primitive permutation groups G is it the case that the conjugates of any proper coset of the point stabiliser cover the non-identity elements of G? Any 2-transitive group has this property, so we have another class lying between primitive and 2-transitive. However, only two examples which are not 2-transitive are known, and they hope to get a complete classification (unlike the case for the class of synchronizing permutation groups).

There were many old friends and the meeting; and it was nice to see Scott Harper, a graduate of the second run of Advanced Combinatorics in St Andrews, now doing a PhD with Tim Burness.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s