Coherent configurations and all that, 1

I’m off to Lisbon next week for three weeks. Among other things, I will be giving four lectures at the Centre for Algebra at the University of Lisbon. One of these will touch on aspects of association schemes and coherent configurations. Since I touched on some of this in my recent post on Boris Weisfeiler, this seems like a good time to get my thoughts together.

In the late 1960s, the same idea arose independently in the USA and the USSR (proof, if proof were needed, of the universality of mathematics – as I write this, I have just been listening to Bob Dylan’s song “A hard rain’s a-gonna fall”, written in the shadow of the Cuban missile crisis). Donald Higman developed coherent configurations, and Boris Weisfeiler cellular algebras. Since, as Jan’s comment on the previous post makes clear, the term “cellular algebras” will just cause confusion with a more recent usage, I will stick to “coherent configurations” here.

To Higman, coherent configurations were combinatorial and algebraic gadgets which could be used to get information about finite permutation groups; they allow one to compute the degrees and multiplicities of the irreducible constituents of the permutation character in terms of combinatorial data; if these degrees and multiplicities don’t turn out to be non-negative integers, then the combinatorial data cannot be realised by the permutation group. (When I was a student in Oxford, he visited the Mathematical Institute and gave a course of lectures on coherent configurations, entitled “Combinatorial considerations about permutation groups”. Susannah Howard and I took notes of the lectures, which were later published by the Mathematical Institute. He was also an examiner of my doctoral thesis, which used these methods heavily.) Higman knew, and pondered, the problem that not every coherent configuration arises from a permutation group, and introduced a condition, the “four-vertex condition”, as an intermediate step.

Weisfeiler, however, made no assumptions about groups. He was concerned with the computational problem of testing whether two graphs are isomorphic, and his construction was a systematic refinement of the graph structure which must be preserved by any isomorphism. So, if two graphs look very much alike but the coherent configurations derived from them are different, the graphs cannot be isomorphic. This technique, under the name “partition refinement”, is an essential ingredient in all modern graph isomorphism packages, as far as I know.

Also, there is a long back story, and an even longer and more complicated sequel.

So what are coherent configurations?

Let X be a finite set. A (binary) relation on X can be regarded as a set of ordered pairs of elements of X, that is, a subset of the Cartesian product X×X = X². The converse of a relation R is the relation R* obtained by reversing all the pairs in R. We can regard a relation as the edge set of a directed graph; for the converse, we reverse all the arrows.

A coherent configuration on X is a collection of relations R_i (where i runs over some index set I) satisfying four conditions:

• The relations R_i, for i∈I, form a partition of X².
• There is a subset J of I such that the relations R_i, for i∈J, form a partition of the diagonal Δ(X) = {(x,x):x∈X}.
• The converse of each relation R_i is a relation R_j (possibly with j = i).
• There are numbers c_ij^k, for all i,j,k∈I, such that, if (x,y)∈R_k, then the number of elements z∈X such that (x,z)∈R_i and (z,y)∈R_j is equal to c_ij^k, independent of the choice of (x,y)∈R_k.

The first three conditions are natural enough, but what is the fourth one doing? To see this, let us represent each relation R_i by a matrix A_i, whose rows and columns are indexed by the set X, with (x,y) entry 1 if (x,y)∈R_i and 0 otherwise. In other words, we take the characteristic function of the set R_i, arranged into the form of a matrix. Now the four conditions for a coherent configuration become:

• The sum of the matrices A_i is the all-1 matrix J.
• There is a subset of the matrices which sums to the identity matrix.
• The set of matrices is closed under transposition.
• For any i,j∈I, we have

  A_i·A_j = Σ_k∈I c_ij^kA_k.

The last condition implies that the linear span of the matrices A_i (over, say, the complex numbers) is closed under multiplication, and so is an algebra. Now the second condition shows that the algebra contains the identity, and the third condition implies (after a short argument) that it is semisimple. So, by Wedderburn’s theorem, it is a direct sum of matrix algebras over the complex numbers. In principle, the degrees of these matrix algebras, and their multiplicities in the natural module CX, can be computed from the parameters c_ij^k.

There are two extreme cases of coherent configurations on X. At one end, we have the discrete configuration, where each relation is a single element of X². At the other end is the indiscrete configuration with just two relations, the diagonal (the relation of equality), and everything else (the relation of inequality).

Now let G be an arbitrary group of permutations of X. Then there is a natural action of G on X², so this set splits into G-orbits. It is completely standard to show that these orbits, regarded as relations on X, form a coherent configuration. The last condition holds because if the relations are orbits, then any combinatorial data must be the same for pairs in the same orbit.

Our two extreme configurations arise in this way: the discrete configuration from the trivial group, and the indiscrete configuration from the symmetric group on X.

This was the inspiration for Higman’s definition, and the basis for his applications of the theory. The algebra spanned by the matrices A_i is the centralizer algebra of the permutation group, and so its degrees and multiplicities are respectively the multiplicities and degrees of the irreducible constituents of the permutation character.

Many other important kinds of combinatorial object are special cases of coherent configurations. These include (just to drop a few names) generalized polygons (invented by Jacques Tits, a former Abel Prize winner), strongly regular and distance-regular graphs, symmetric and quasi-symmetric designs, partial geometries, …

Now we turn to Weisfeiler’s end of the story. From now on, I won’t distinguish between a coherent configuration and the (cellular) algebra spanned by the matrices A_i.

The partitions of a set Y, ordered by refinement, form a lattice. (In other words, a partition σ is below another partition ρ in the order if σ refines ρ, in other words, if each part of σ is contained within a single part of ρ.) The meet of two partitions ρ and σ is thus their coarsest common refinement; its parts are all non-empty intersections of a part of ρ and a part of σ. Once we have the meet of two elements in a finite set, we can define the join in a very general way: the join of ρ and σ is the meet of all those partitions which are coarser than both ρ and σ. (There is always at least one such partition, namely the partition with a single part.) There is a more combinatorial description of the join of ρ and σ. The part containing a point y consists of everything that can be reached by a walk which alternately moves to a point in the same ρ-class and then to a point in the same σ-class.

Now of course this applies to partitions of the set X²; but what happens when we restrict our attention to coherent configurations, which are just very special partitions?

Theorem The join of coherent configurations is a coherent configuration.

This theorem was proved by Higman; I don’t know if he was the first. A proof by direct combinatorial methods is quite a challenge, given the rather complicated definition of join. Fortunately, there is a simpler way. We observe that a matrix is constant on the parts of the partition defined by a coherent configuration C if and only if it is a linear combination of the basis matrices A_i, that is, lies in the algebra spanned by these matrices. Now the matrices constant on the join of C₁ and C₂ are precisely those constant on both C₁ and C₂, and hence those which lie in the intersection of the two algebras. But this intersection is again an algebra!

Now we reverse the above argument. There is an operation of “meet” on coherent configurations, which is not their meet as partitions: the meet of C₁ and C₂ is the join of all coherent configurations finer than both C₁ and C₂. For this to make sense, we need to know that there is at least one such coherent configuration; but the discrete configuration fills the bill here.

So the coherent configurations on X form a lattice. The bottom element is the discrete configuration, and the top element is the indiscrete configuration.

In fact, the argument gives more:

Theorem Given any partition ρ of X², there is a unique coherent configuration which is the coarsest such configuration finer than ρ.

For we simply take the join of all the coherent configurations finer than ρ, noting that there is always at least one such configuration, namely, the partition into singletons. We will call this the coherent refinement of ρ.

Now here is partition refinement in a nutshell. Given a graph on the vertex set X, there is a partition of X² into three parts, namely the pairs (x,y) with x = y, with x joined to y, or with x not joined to y. Any graph isomorphism must preserve the coherent refinement of this partition. Maybe this is enough to tell that two given graphs are not isomorphic. Otherwise, we could ask whether the vertex x could map to a specific vertex of the other graph. Now we refine our previous partition by making {(x,x)} a part, and once again compute the coherent refinement; continue until either we have told the two graphs apart, or we have mapped one to the other by a function preserving all the partitions found, and in particular preserving the original graph.

The theory of coherent configurations is a theory of finite objects, so it may be worth noting that one can define a “lattice of all finite coherent configurations”, an infinite object. To do this, we embed a coherent configuration on the set {1,…,n} to one on the set {1,…,n+1} as follows:

• Each part of the original configuration is a part in the new one.
• If F is a fibre of the original configuration (a part of the partition of the underlying set induced by the relations contained in the diagonal), then we let {(x,n+1):x∈F} and its converse be parts.
• Finally, there is a part {(n+1,n+1)}.

Now we take the direct limit.

I have no idea whether this construction has any use at all.

In the sequel to this post I will discuss association schemes (precursors of coherent configurations introduced first in statistics). From one point of view, they are very natural, since they simply replace the complex numbers by the real numbers; from another point of view, they are very unnatural, since the meet of association schemes is not defined. They have also caused some controversy in the question of naming, since the name “association scheme” has been indiscriminately applied to various other types of structure, including coherent configurations. Finally, the failure of meet for association schemes leads to some interesting questions about permutation groups.