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 = X2. 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 Ri (where i runs over some index set I) satisfying four conditions:

  • The relations Ri, for iI, form a partition of X2.
  • There is a subset J of I such that the relations Ri, for iJ, form a partition of the diagonal Δ(X) = {(x,x):xX}.
  • The converse of each relation Ri is a relation Rj (possibly with j = i).
  • There are numbers cijk, for all i,j,kI, such that, if (x,y)∈Rk, then the number of elements zX such that (x,z)∈Ri and (z,y)∈Rj is equal to cijk, independent of the choice of (x,y)∈Rk.

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

  • The sum of the matrices Ai 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,jI, we have

    Ai·Aj = ΣkI cijkAk.

The last condition implies that the linear span of the matrices Ai (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 cijk.

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 X2. 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 X2, 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 Ai 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 Ai.

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 X2; 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 Ai, that is, lies in the algebra spanned by these matrices. Now the matrices constant on the join of C1 and C2 are precisely those constant on both C1 and C2, 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 C1 and C2 is the join of all coherent configurations finer than both C1 and C2. 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 X2, 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 X2 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):xF} 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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history and tagged , , , . Bookmark the permalink.

8 Responses to Coherent configurations and all that, 1

  1. Pingback: Brain Boost* « Log24

  2. Misha Klin has sent me a lot of information about the topic of this post. I will digest it and say something (including links) later in this series.

  3. Bjarki Holm says:

    Dear Peter,

    Thanks for a very nice summary of the development of coherent configurations.

    Reading this, I have one question: when you define the algebra associatied with a coherent configuration, you consider the linear span of the basis matrices Ai over the complex numbers. Do you know if there is any particular reason to study these algebras over the complex numbers? This seems a bit strong as we really only need integral linear combinations of the basis matrices, via the numbers c_{ij}^k.

  4. That is a very good question. The definition works over the integers, as you say. But the most powerful results come from looking at the representation theory of the algebra, and even the difference between the complex and real numbers makes a big difference. In fact, statisticians (to whom all data is real) only work over the reals. I will come back to this point sometime, and try to say a bit more.

  5. Durga says:

    If I see coherent algebra as a tool to attack graph isomorphism problem as did by Weisfeilear without invoking group theory, I want to understand what is the meaning of clousure under transpose. I think i have intuitive understand of other conditions based on complet colouring of graph, sum being J means theat set of relation is partitioin, some subset adding to I means that diagonal elements are coloured differently than non-diogonal elments, closure under matrix multiplication has to do with partition being equitable. So what is the similar understanding of requiring closuer under transpose?

    • If you didn’t have closure under transpose, then you could refine your relations still further, by intersecting them with their transposes, since a potential isomorphism preserving a bunch of relations also preserves their transposes.

      • Durga says:

        So, if our interest is only graph isomorphism problem then is it better not to necessiate clousre under transpose to get finer partition? Would the still result in cellular algebra, primarly the unique (0-1) basis of the algebra?

      • Sorry, I don’t understand why, trying to do graph isomorphism, you throw away some cheap information.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s