Bases

A base for a permutation group is a sequence (a₁,…,a_r) of points in the permutation domain whose pointwise stabiliser is the identity. Bases were introduced in computational group theory by Charles Sims, since two elements of a permutation group are equal if and only if they agree on a base. So it is useful to find a small base.

A base is irredundant if no point in the base is fixed by the stabiliser of its predecessors; it is minimal if no point in the base is fixed by the stabiliser of all the others. An irredundant base can be found simply by choosing and stabilising points not already fixed there are no more. By contrast, it is more difficult to find a minimal base.

A couple of things are clear:

• any minimal base is irredundant (but the converse is false);
• any re-ordering of a minimal base is minimal (but this is not true for irredundant bases).

In 1995, Dima Fon-Der-Flaass and I showed that the three conditions on irredundant bases, namely

• they are preserved by re-ordering;
• they all have the same size;
• they are the bases of a matroid;

are all equivalent. We call groups having this property IBIS groups.

Recently several people (Murray Whyte, Scott Harper, Pablo Spiga, maybe others) asked whether the set of sizes of irredundant bases form an interval. This would be an analogue of a result of Tarski about generators of an algebra.

After Pablo asked me this, I started thinking about it. So let G be a permutation group which has an irredundant base of size x and one of larger size y, and let z be a number between x and y: is there an irredundant base of size z?

The easiest case to think about is x = 1; to my delight, this case is just Mornington Crescent (if you know what this is). You start working along the longer base, stabilising the points; after a while you get bored, say “Mornington Crescent”, and play the point in the short base, at which point the game terminates and you have an irredundant base.

(I had always regarded Mornington Crescent as an analogy for nuclear war; it is nice to find a less destructive interpretation of it!)

The proof in the general case is just a variation on this. Now you can’t win in just one step. Suppose for a contradiction that there is no irredundant base of size z. Choose points in the long base, and when you get bored, switch to the small base, so that you have z altogether. By assumption, this base must be redundant; but the points in the long base are irredundant, so the redundancies must be in the short base. Throw them away. Now play the game again, continuing a bit longer with the long base and then just using the remaining points of the short base, to get z altogether. This procedure can be repeated forever, contradicting the fact that the natural numbers are well-ordered (so it is not possible to throw away points from a finite set for ever). The contradiction shows that the assumption is wrong, there is an irredundant base of size z. This proof is nonconstructive, but you can easily turn it into an algorithm.

What about minimal bases?

The analogue for minimal bases is false. For any integer d > 1, there is a group whose minimal bases have sizes 1 and d only. (Take an elementary abelian group of order p^d, and let it act with one regular orbit and d independent orbits of size p. One point from each of the short orbits gives a minimal base; but any base with fewer than d points must contain a point from the regular orbit, so is minimal only if it has size 1.)

However, it is not yet known whether they do form an interval if the permutation group is required to be transitive. This seems much more difficult. Here is a possibly representative example.

Take the symmetric group of degree n, acting on the set of 2-element subsets of {1,…,n}. A set of points in the permutation domain is the edge set of an n-vertex graph; it is a base if and only if there is no isolated edge and at most one isolated vertex. It is easy to see that a minimal base can contain no cycles, so is a forest. Now a star on all but one vertex gives a minimal base of size n−2 (the smallest possible). All smaller sizes down to roughly 2n/3 (the actual size depending on the congruence class of n mod 3) can be realised by forests whose components are stars.

A further question is: What happens for greedy bases? One of these is found by choosing the next base point in an orbit of maximum size for the stabiliser of its predecessors. (There is some variability because there might be a number of orbits of the same size.)