In the last week I let myself in for giving four talks: two seminars here (the London Algebra Colloquium and the Combinatorics Study Group); a public lecture at Royal Holloway commemorating Coulter McDowell, a former head of department; and a lecture at Anthony Hilton’s “Old Codgers’ Meeting” in Reading. Getting to Reading on a day of a tube strike was quite challenging; I walked from home to Paddington station (in two hours and ten minutes) and took the bus back (only half an hour quicker).
Anthony persists in putting the apostrophe in the wrong place in the conference title, suggesting that there is only one old codger, presumably him. In fact, anyone can come, but only old codgers are allowed to speak. I am not quite an old codger yet, but was allowed to be an honorary old codger for the occasion.
There is always some discussion about what the word “codger” means. A codger has to be elderly and eccentric, possibly with an air of grumpiness, but the word is generally a term of affection.
This year’s Old Codgers’ Meeting commemorated David Daykin, who was on the staff at Reading for many years and died this August (there is an obituary here). I knew him, but not closely; from the reminiscences, it seems clear that he qualified as an old codger.
I only once worked with David, on the “intricacy” project which I have described on this blog. But his many interests included set families, so I decided to speak about these. I had an ulterior motive too. Dima Fon-Der-Flass also died in the past year, and he and I wrote a paper about set families, matroids, and groups, which I believe deserves to be better known than it is. So I thought I would post a summary here.
Matroids were invented by Whitney to capture the notion of linear independence in a vector space. There are many ways of defining a matroid, but for my purposes here a definition in terms of bases is best. A non-empty family of subsets of a set is the family of bases of a matroid if it satisfies the exchange property, that is, given any two sets A and B in the family, if e is any element lying in B but not in A, then we can add e to A and remove an element not in B to obtain another basis. This condition implies that any two bases have the same cardinality, and lies behind standard dimension theory for vector spaces.
In a matroid, a subset of E is independent if it is contained in a basis; a set is a flat if it consists of all points which are dependent on a fixed independent set.
There are many parts of mathematics where “bases” arise but where the exchange axiom is not necessarily satisfied. These include minimal generating sets for algebras, and bases for permutation groups (which I will discuss below). Dima and I proved a nice theorem about when such “bases” do form the bases of a matroid. But Dima noticed that the result had a general formulation in terms of families of sets, as follows.
Given a family F of subsets of a set X, let Z be the intersection of all the sets in F. We say that a list (S1, S2, …) is a base for the family if the intersection of the sets in the list is equal to Z. Moreover, we say that the list is irredundant if no set contains the intersection of its predecessors. Our theorem says that the following three conditions are equivalent:
- all irredundant bases have the same cardinality;
- the irredundant bases are preserved by re-ordering;
- the irredundant bases satisfy the exchange property, and so form the bases of a matroid.
We called a family of sets satisfying this condition an IBIS family (an acronym for Irredundant Bases of Invariant Size).
In the seminar where we announced our results, Dima produced on the blackboard a lovely drawing of an ibis sitting on its eggs. Unfortunately this was before the days of camera phones, and the picture has been lost for good. But here as a substitute is a picture of an ibis that I took in Brisbane, which I intended to use to illustrate a monograph on the subject (which never got written).
Every matroid arises in this way, so IBIS families are as general as matroids; and the argument shows that they do have some extra flexibility. Let M be a matroid on E. A family S of flats is called separating if, for any independent set I and any element e of I, there is a flat in S intersecting I in all its points except e. Note that S is separating if and only if it contains all hyperplanes. We allow S to be a multiset; flats in S can have arbitrary positive multiplicity. Then the dual of S is an IBIS family representing the given matroid.
This isn’t how we began, so let me sketch the permutation group connection. Let G be a permutation group on a set E. A base for G is a sequence of points of E whose pointwise stabiliser is the identity; it is irredundant if no point is fixed by the stabiliser of its predecessors. Now, although the words have apparently changed their meanings, the previous theorem remains true: the three conditions written down above are equivalent. To see this, we apply the “IBIS family” theorem to the family of point stabilisers (which are subgroups of G, though we treat them as subsets for this purpose).
Of course, a permutation group satisfying these equivalent conditions is called an IBIS group.
An IBIS group acts as a group of automorphisms of the corresponding matroid. The action has a particular property: the pointwise stabiliser of any set fixes pointwise the flat it spans. This is almost equivalent to being an IBIS group: if we add the condition that no point outside the flat is fixed, then the group is necessarily IBIS.
For example, the general linear group on a vector space is an IBIS group, but the projective general linear group acting on the projective space is not (unless the underlying field has just two elements).
Using the Classification of Finite Simple Groups, Tracey Maund determined all IBIS groups which act transitively on the set of bases of their matroids, provided that the rank is at least 2. Boris Zilber gave a completely different argument, geometrical and model-theoretic, avoiding the use of CFSG but requiring rank at least 7.
Several open problems remain:
- Which matroids arise from IBIS families of subgroups of a group? (If the family of subgroups is closed under conjugation, then the group can be represented as an IBIS permutation group; not all matroids can occur here.)
What about IBIS families of substructures of other kinds of structure
(subrings of a ring, sub-Latin squares of a Latin square, etc.)?
- Which set families, or permutation groups, have the weaker property that all minimal bases have the same size? The minimal bases need not be the bases of a matroid in this case; is there a theory of the structures that arise in this way? (There are things called greedoids, which generalise matroids, but these are not they. In a greedoid, all bases do have the same size, but they are not preserved by reordering; in our case, minimal bases are clearly preserved by reordering but may have different sizes.)
There is a greedy algorithm for choosing an irredundant base for a set family (or permutation group): choose each set in the sequence so that it meets the intersection of the sets chosen so far in as small as possible a subset. What can be said about the three conditions
- all greedy bases have the same size,
- the greedy bases are preserved by re-ordering,
- the greedy bases are the bases of a matroid,
apart from the fact that they are not equivalent?