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!