Terminology: association scheme or coherent configuration?

At the Villanova conference, many of the talks were about association schemes or coherent configurations, or indeed generalisations of these. A certain tension between different uses of these terms was evident. I’d like to set down my own views here.

The objects

A coherent configuration (in brief, a CC) consists of a finite set X and a partition P of X×X (the parts of such a partition are binary relations on X) satisfying the following three conditions:

  1. the diagonal {(x,x):xX} is a union of parts of P;
  2. the transpose R* of a relation R in P is also in P;
  3. the span (over the complex numbers) of the relation matrices of the relations in P (the X×X matrices each having 1 in the positions (x,y) belonging to the corresponding relation and 0 elsewhere) is closed under multiplication, and so an algebra (often called the Bose–Mesner algebra of the configuration).

The third condition can be expressed combinatorially, in terms of paths of length 2, but it is not necessary to spell out the details here.

There are three important specialisations of the notion.

  • A CC is called homogeneous if, in condition 1, the diagonal of X is a single relation.
  • A CC is called commutative if the algebra in condition 3 is commutative; that is, the relation matrices commute.
  • A CC is called symmetric if the relation matrices are all symmetric; that is, in condition 2 we have R* = R for each relation R in P.

These conditions become stronger as we go down the list; that is, every symmetric CC is commutative, and every commutative CC is homogeneous.

The problem arises because the alternative term association scheme (or AS for short) has been applied by some authors to each of the four concepts just defined: thus, an AS is a symmetric CC, or a commutative CC, or a homogeneous CC, or simply a CC.

After a little excursion into terminology for groups, I will give a very short historical account of how the present muddle came about, and then argue that we should in fact stick to the terminology I defined above wherever possible.

Terminology for groups

Group theory is a rich subject with nearly 200 years of history, and the term “group” has been embellished by many prefixes, suffixes, and qualifying adjectives. These appear to fall into five main types.

  • Generalisations of groups: semigroup, quasigroup, hypergroup, pseudogroup, groupoid, quantum group.
  • Specialisations of groups: abelian group, nilpotent group, simple group, profinite group, and many many others.
  • New groups from old: subgroup, factor group, quotient group, product group; the term “derived group” appears to belong here but it is better described as “commutator subgroup”, a special kind of subgroup.
  • Concrete groups: permutation group (one whose elements are permutations and whose operation is composition), matrix group (one whose elements are matrices and whose operation is matrix multiplication), black box group (one whose elements are bit-strings and whose operation is given by an oracle).
  • Groups constructed from other things: Galois group, fundamental group, cohomology group, automorphism group.

The types relevant to this inquiry are the first two, so I will say a bit more about these.

Obviously there are huge numbers of specialisations of groups, so many that if the word “group” is qualified by an unfamiliar term, our first thought is that it refers to a specialisation. By contrast, the class of generalisations of groups has very few members, almost all following a common pattern: a “semigroup” satisfies half of the group axioms, “quasigroups”, “pseudogroups” and “groupoids” are not really groups at all, a “hypergroup” goes beyond a group in some way. These prefixes and suffixes are used in the same way in many other parts of mathematics, as for example “pseudomanifold”, “semiring”, “quasi-symmetric design”, and “ovoid”. The term “quantum” is acquiring the same connotation: nowadays it sometimes seems as if you can put the word in front of any mathematical concept. (I have a paper on “quantum chromatic number” of a graph.)

The only other common use of a qualifying word for a generalisation is of negative words which are really just used for emphasis: a “non-commutative ring” is a ring which is not necessarily commutative, and a “non-associative algebra” is an algebra which is not necessarily associative. The words are not really necessary.

Some history

The concept of association scheme, meaning “symmetric CC”, was introduced by Bose and Mesner in 1959 in connection with partially balanced designs. A block design is partially balanced if there is an association scheme on the set of points (or treatments) so that the number of blocks containing two points depends only on the “associate class” (the relation of the CC) which contains them. However, the notion of partially balanced design was introduced much earlier, by Bose and Nair in 1939, and further developed by Bose and Shimamoto in 1952.

In my view the most important milestone for algebraic combinatorics was the appearance of Philippe Delsarte’s PhD thesis on The association schemes of coding theory in 1973. Delsarte used the term association scheme to mean a commutative CC, but in fact all his important examples are symmetric. He showed how many concepts from both coding theory and combinatorial design theory can be put into a unified framework of association schemes, and proved strong and influential bounds on their cardinalities using a linear programming method which he introduced.

In 1984, Bannai and Ito published the first volume of their book Algebraic Combinatorics. They used the term association scheme to mean a homogeneous CC, although one participant at the Villanova conference remarked to me that he thought this was a temporary lapse of concentration, since like Delsarte all their important examples are symmetric.

Earlier, two very important developments had taken place, independently of each other. Weisfeiler and Leman in the Soviet Union and Higman in the USA defined the general notion of a coherent configuration and developed the properties of CCs.

Of course they did not use the same terminology. Weisfeiler and Leman referred to a cellular algebra for an inessential generalisation of a CC; this term fell somewhat out of use, and in the meantime Graham and Lehrer used it for a completely different object. So now “coherent configuration” has become accepted. Igor Faradjev’s software package for computing with these objects goes by the name CoCo.

The emphasis was quite different. All four types of objects defined above are closed under join (in the lattice of partitions of X×X), but only CCs are closed under meet. This is because there is a trivial “discrete” CC on a set X (the partition into singletons); no such element exists for the other classes. Thus any partition of X×X has a unique coarsest CC which refines it, and this CC is invariant under all automorphisms of the original partition. This was important for Weisfeiler and Leman who used this approach on the graph isomorphism problem, and it was exploited to great effect by Babai in his elementary bounds for base size and order for primitive permutation groups.

Higman, on the other hand, was more concerned with the algebraic approach. First observe that, if G is any permutation group on X, then the orbits of G on X×X form a CC. Higman called this the group case; the CC is now often referred to as Schurian. Also, given the structure constants (the intersection numbers) of the CC, one can in principle compute the decomposition of the algebra generated by the relation matrices, and in particular exploit the fact that degrees and multiplicities of irreducible representations must be integers to obtain non-existence results for certain kinds of permutation group.

Which terminology?

It is a pity that both terms “association scheme” and “coherent configuration” are long and unweildy. Indeed, it is for this reason that I have consistently abbreviated them. Group theory benefits enormously from the short and pithy name of the central concept!

For reasons suggested earlier, it makes more sense to name the most general concept in common use and then add qualifying words to define specialisations. This is what I have done above, and the terminology I have used is surely unexceptionable.

But what should an “association scheme” be? This is where the disagreement comes in.

There were two good reasons why Bose and his various collaborators used the term for a symmetric CC. First, the way the concept arises in defining partially balanced designs, it will always be symmetric. Second, much statistical analysis involves decomposition of real vector spaces. Experimental data comprises a list of numbers, a vector in a real space, and we wish to decompose this space into subspaces corresponding to the overall mean, treatment and nuisance effects, and so on. The relation matrices of a symmetric CC are commuting real symmetric matrices, and so can be diagonalised by an orthogonal transformation of the space; then the projections of the data onto various interesting subspaces give information about the result of the experiment.

So it is certainly true that statisticians need a name for a symmetric CC. Since they invented the term “association scheme”, this seems appropriate for the job.

A much less significant reason was apparent in some investigations I did with Cristy Alejandro and Rosemary Bailey some years ago. Among other things, we called a permutation group G AS-friendly if there is a unique finest association scheme preserved by G, and AS-free if the only association scheme preserved by G is the trivial one. Thus, an AS-free group is AS-friendly.

Here, I am using “association scheme” in Bose’s sense. If similar definitions of “CC-friendly” and “CC-free” were made, then closure of CCs under meet implies that every permutation group is CC-friendly, and only 2-homogeneous groups are CC-free. With AS in place of CC, things are much more interesting, as we indeed found!

If we wanted to extend the usage of “association scheme”, I think a weak case could be made for extending it to commutative CCs. There is a huge difference in the algebraic structure of commutative and non-commutative CCs, coming from the fact that commuting matrices can be simultaneously diagonalised. This means that all the irreducible representations of the algebra are 1-dimensional, and the common eigenspaces of the matrices form a decomposition which includes the one the statisticians need. This case is also the only one in which any reasonable theory of duality exists, similar to the duality for abelian groups. However, as both Delsarte and Bannai & Ito knew, the important examples are all symmetric.

It might be thought that there is an argument for drawing a clear line between homogeneous and inhomogeneous CCs, similar to that between transitive and intransitive permutation groups. In fact this is not so clear. Certainly we classify intransitive groups using the fact that they are subdirect products of transitive groups, just as for association schemes in the very nice talk by Matan Ziv-Av at the Villanova conference. This argument actually requires us to think of the homogeneous and inhomogeneous CCs as the same kind of object, described by the same name.

Indeed, the line between “imprimitive” and “primitive” is arguably more important for permutation groups! So far as applications are concerned, for the application to graph isomorphism it is crucial to have general CCs, and for the algebraic theory applied to permutation groups it works virtually identically for homogeneous and inhomogeneous CCs.

There are some techniques (notably the theory of Schur rings and the work of Paul Terwilliger) where homogeneity is important; but I am not sure that this overrides the general view I have taken.

My proposal, then (which I am absolutely sure will not prevail) is to use the term “coherent configuration” with suitable qualification, and to reserve the term “association scheme” for symmetric CCs.

About these ads

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.

2 Responses to Terminology: association scheme or coherent configuration?

  1. Dima says:

    Only someone who never really read Bannai and Ito’s book would remark that they actually meant symmetric assoc. schemes only. They do give a plenty of non-symmetric examples.

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