Dima Fon-Der-Flaass

Yesterday, Edwin van Dam reminded us of a conjecture he and Willem Haemers made ten years ago: almost all graphs are determined by their spectra. This contrasts with the situation for special classes of graphs such as trees, and indeed distance-transitive graphs, the real subject of his talk. The latter follows from a theorem of Dima Fon-Der-Flaass about the existence of large families of strongly regular graphs with the same parameters (and hence the same spectra).

After the break, Elena Konstantinova found me and gave me a copy of the book commemorating Dima’s life, that she and Dima’s parents had produced after his death in 2010. She had sent all the contributors a copy but somehow mine had gone astray and never arrived.

It is a lovely book and a beautiful tribute to Dima, someone who walked lightly on the earth but made a lasting impression on everyone he met. But on reading it, I was struck by something, and I would like to talk about it here.

In the introduction to the book, Dima is quoted as saying,

The best way to honour the memory of a mathematician is to think about the mathematical problems he posed.

But in doing this we should remember something else. Recently I discussed Persi Diaconis’ challenge to us to draw a line between “recreational” and “serious” mathematics, and gave us a powerful argument that no such line existed, since considering card shuffling leads quickly to the Artin conjecture, which is known to be true modulo the generalised Riemann hypothesis. I think that Dima’s life and work poses a similar challenge: draw a line between “olympiad” and “serious” mathematics. I believe the answer is similar. Dima’s olympiad problems were sometimes themselves serious mathematical research; and very often they required techniques which the future mathematician would often find of use. Dima’s own mathematics touched on very serious concerns.

In the book, a number of people discuss his work in graph theory, specifically in algebraic graph theory (notably distance-regular graphs). This was not my view of Dima. I will discuss three topics he worked on, none in algebraic graph theory, and pose some questions (or suggest some investigations) he left unfinished.

Orbits on antichains

In 1993, Dima published a paper in the European Journal of Combinatorics proving a duality conjecture of Deza and Fukuda. The original conjecture concerned families of subsets of a set; Dima re-formulated it much more generally, in terms of antichains of ranked posets, and proved it in this generality.

In a poset, there are natural bijections from antichains to down-sets to up-sets to antichains, as follows:

• Given an antichain A, map it to the up-set of elements lying above some element in A.
• Given an up-set, its complement is a down-set.
• Given a down-set, map it to the antichain of its maximal elements. (This is the inverse of the first operation, with the order reversed.)

The composition of these maps is not the identity, so we have a naturally defined permutation f on the set of antichains. This permutation was the object of Dima’s study.

About the same time, Michel Deza drew my attention to Dima, describing him as “my mathematical son” because of his wide range of interests. We managed to get money to bring him to London as a postdoc. Although the nominal subject of the project was coding theory (specifically bent functions), Dima needed no encouragement to continue to be interested in everything. Among other things, we wrote a sequel to the antichains paper, less satisfactory than the original perhaps, but more open-ended.

I am sure that there is more to do here to understand these ideas better.

IBIS families

I was interested in the relationship between bases for a permutation group (sequences of points with pointwise stabiliser trivial) and bases for a matroid. Dima and I proved a very nice theorem. A base for a permutation group is irredundant if no point is fixed by the stabiliser of its predecessors. (This requires the base to be an ordered sequence.) Now the following conditions for a permutation group are equivalent:

• all irredundant bases have the same size;
• the irredundant bases are preserved by reordering;
• the irredundant bases are the bases of a matroid.

We called permutation groups with this property IBIS groups (an acronym for “Irredundant Bases of Invariant Size”), and posed the problem of classifying them. This problem is still unsolved. A somewhat easier problem, also unsolved, is that of classifying the matroids which can arise from IBIS groups.

However, Dima put the problem into a new and much more general context. We are given a family (S_i:i∈I) of sets indexed by a set I. We define a base for the family to be a sequence of indices such that the intersection of the corresponding sets is equal to the intersection of the entire family; a base is irredundant if the intersection of the corresponding sets is not the intersection of any subcollection of them. Now the same theorem as stated above holds for arbitrary families of sets! Moreover, every matroid is represented by an IBIS family of sets!

In the permutation group case, the IBIS family is a conjugation-closed family of subgroups of the group (the point stabilisers). So we could ask, which matroids are represented by IBIS families of subgroups in general (not necessarily closed), or of other distinguished kinds of subgroups. I believe that all these questions are completely open.

Three extensions of trees

There are many ways of extending the notion of tree. Three of particular interest in algebra (specifically group theory) are Λ-trees (where Λ is an ordered abelian group), twin trees, and buildings. It would take me too far afield to give definitions of all these things, so I will simply make patterns with words.

These three extensions are in some sense “orthogonal”, meaning that they can potentially be combined in any fashion, as the diagram shows.

Apart from trees at the very bottom of this diagram, the objects have been almost entirely the province of algebraists: Λ-trees in geometric group theory (the subject that used to be called “combinatorial group theory”), where my ex-colleague Ian Chiswell has written the definitive book, and buildings and twin trees (and indeed twin buildings) in the theory of algebraic groups and related things such as Kac–Moody groups.

Because of this separation of fields, it is the case that we haven’t achieved the diagram completely: twin Λ-trees and Λ-buildings are still only words without concepts.

Dima rescued twin trees for combinatorics, by giving a very general combinatorial construction showing that they were far more prolific and varied than had been previously thought. He started thinking about twin R-trees.

A fitting memorial to him, in accordance with his own views, would be a theory covering the entire diagram. It may seem odd that a general theory should commemorate a skilled problem-solver, but Dima was always more than that …