The Wall conjecture extended

Tim Wall boldly conjectured in 1961 that the number of maximal subgroups of a finite group G is at most |G|−1. (This would be best possible, since the the elementary abelian 2-group attains this bound.) He proved that the conjecture holds if G is soluble. The conjecture itself was disproved by participants in an AIM workshop in 2012, but in the meantime, Martin Liebeck, Laci Pyber and Aner Shalev had proved that the number of maximal subgroups is at most c|G|3/2. (The report of the workshop notes that the counterexamples have order smaller than |G|1+a, where a < 1/1000 (and possibly much smaller).)

The partition into right cosets of a subgroup of a group G is a system of imprimitivity for G in its regular action on itself by right multiplication, and in particular, maximal subgroups correspond to systems of maximal blocks. So, in our work on the Road Closure conjecture (described here), João Araújo and I speculated that the results on Wall’s conjecture might extend to the number of systems of maximal blocks of imprimitivity for all finite transitive permutation groups.

This did indeed turn out to be the case. Mariapia Moscatiello from Padova, who is visiting our department this month, gave a seminar talk on Wednesday, in which she showed that exactly the same bounds (cn3/2 for arbitrary transitive groups of degree n, and n−1 for finite soluble groups) hold for the more general problem. This lovely result is joint work with Andrea Lucchini and Pablo Spiga. Their paper is on the arXiv: 1907.08477.

So one (rather important) question remains. Is there an efficient algorithm to find all the maximal blocks through a point in a transitive permutation group? In particular, can this be done in polynomial time? An efficient algorithm would almost certainly allow us to push further with our computational test of the Road Closure conjecture. In the computation as we have done it so far, we use the fact that all the minimal blocks through a point can be found efficiently, and then climb up to the top of chains of blocks; this is very inefficient since we pass all possible blocks on the way and there may be very many of these!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.