Symmetry vs Regularity

This is the title of a conference to be held next year (2018) from 1 to 7 July, in Pilsen, Bohemia, Czech Republic. The subtitle is “The first 50 years since Weisfeiler-Leman stabilization”, and the webpage is here.

If you have heard Laci Babai talking about his quasi-polynomial time algorithm for graph isomorphism, you might appreciate the significance of this; but if not, it might look a bit specialised. I want to say a bit about the subject matter of the conference, and persuade you that it is a central area of algebraic combinatorics which connects with many other areas of mathematics.

The area grew from three input streams, which resulted in three different names and some continuing confusion. I’ll describe them one at a time, and say a bit about the subsequent history.

Association schemes in design of experiments

If you design an experiment for comparing a number of factors, you have to look ahead to how useful information will be extracted from the experimental results. In all but the simplest cases, this involves finding a generalized (von Neumann) inverse of a potentially rather large concurrence matrix.

R. C. Bose and his school invented the concept of partially balanced designs to facilitate this, replacing inverting a large matrix to inverting a much smaller matrix. This tylically involves having a structure known as an association scheme on the set of treatments, so that the number of blocks in which a pair of treatments occur depends only on the associate class containing the pair of treatments.

So let us stop and define this object. It is a partition of the set of all ordered pairs from the set X of treatments into relations R0, … Rs, with the properties

  • each Ri is symmetric;
  • the diagonal {(x,x):xX} is a single relation, say R0;
  • for all i,j,k, and all pairs (x,y) in Rk, the number of zX such that (x,z)∈Ri and (z,y)∈Rj depends only on i,j,k, and not on (x,y); these numebrs are denoted by pijk.

The third condition looks complicated, but it simply says that the linear span over the real numbers of the matrices of the relations is closed under multiplication, and so forms a commutative algebra, which is called the Bose–Mesner algebra of the association scheme. From the point of view of the statistician, inverting an n×n matrix is replaced by inverting an element of this algebra (represented by an (s+1)×(s+1) matrix in the regular representation, usually very much smaller.

The smallest non-trivial case is s=2, where the relations R1 and R2 are the edge sets of a complementary pair of strongly regular graphs.

The Bose–Mesner algebra thus has two bases: the first consists of the relation matrices; the second consists of the orthogonal projections onto the eigenspaces. The change of basis matrices between these two are now denoted by P and Q.

Cellular algebras in graph isomorphism

The second stream flowed from the former Soviet Union, in particular from the work of Weisfeiler and Leman on graph isomorphism. They defined a class of combinatorial structures, which now are called coherent configurations for reasons we will see shortly; these generalise association schemes in two ways. Again we partition the set of ordered pairs into relations, but we weaken the first two conditions as follows:

  • the transpose of any relation R in the configuration is another relation (not necessarily the same as R);
  • the diagonal is a union of some of the relations in the configuration (not necessarily just one).

The third condition remains the same; so the relation matrices once again span an algebra, though this is no longer necessarily commutative. This algebra was called a cellular algebra, but this term has been hijacked to have a completely different meaning. Taking terminology from the third stream, we call the set-up a coherent configuration, and the algebra a coherent algebra.

How is this relevant to graph isomorphism? We begin by remarking that, if we could find (generators for) the automorphism group of a graph, we could solve graph isomorphism. For, given two graphs, without loss of generality they are both connected; now the two graphs are isomorphic if and only if their disjoint union admits an automorphism interchanging the two components.

Now given a graph, we think of it as a partition of the set of ordered pairs into three parts: the diagonal; the edges of the graph; and the non-edges of the graph.

Now, given any partition of the pairs, we can refine it to a partition which is an association scheme, and can be computed effectively from the graph. First, for each triple i,j,k of indices of relations, and each pair (x,y) in Rk, we count the number of points z such that (x,z)∈Ri and (z,y)∈Rj; then we split Rk into parts corresponding to the different values of this parameter. We repeat this process until it stabilises; when this happens, the values pijk are well-defined, and we have a coherent configuration.

Moreover, this configuration is invariant under the automorphism group of the graph. If it is the trivial configuration, in which all parts are singletons, then the automorphism group is the trivial group. Otherwise, we can try to show that there is a vertex whose stabiliser is trivial, by splitting one of the diagonal relations into a pair (x,x) and all the rest, and repeat the refinement. I will not give further details. But the upshot is that we would like to find a reasonably small set of vertices whose pointwise stabiliser is trivial, and then work back to find appropriate automorphisms.

Coherent configurations and permutation groups

The third strand is the oldest, going back to Schur, who invented the method of Schur rings in his proof that a primitive permutation group containing a regular cyclic subgroup of composite order must be doubly transitive. The method was developed by Schur’s student Wielandt, and included as the fourth of five chapters of his influential book on permutation groups. The translation, by R. Bercov, was my own introduction to the subject in 1968.

Wielandt’s book in fact segues from Schur rings into representation theory, and it is clear that he had thought deeply about this transition. But he didn’t publish much, and the idea was taken up by Donald Higman in the late 1960s. Higman defined a coherent configuration, as we have done above, and observed that, if G is any permutation group, then the orbits of G on ordered pairs form a coherent configuration.

If this configuration is an association scheme, then the group will act on the eigenspaces of the Bose–Mesner algebra, and indeed will be irreducible on each eigenspace. Higman saw the general theory as a way of decomposing permutation representations into irreducible components. Things are more difficult because of the non-commutativity, but the closure under transposition has the result that the algebra is semisimple, so is isomorphic to a direct sum of matrix algebras. In principle, the dimensions of these matrix algebras and their multiplicities in the Bose–Mesner algebra can be computed from the parameters of the configuration. In the group case, this algebra is precisely the centraliser of the permutation matrices making up the group; so on interchanging degrees and multiplicities, we get information about the representation of the group and its decomposition.

Higman spent the year 1970–1971 in Oxford; he was the external examiner for my doctorate, and he gave a course of lectures, for which I took notes (along with Susannah Howard), which were subsequently published in the Mathematical Institute’s Lecture Note Series. So I was in at the ground floor!

Subsequent developments

We are now faced with four kinds of objects; in order of increasing generalisation, these are association schemes (symmetric coherent configurations), commutative coherent configurations, homogeneous coherent configurations (those for which the diagonal is a single relation), and general coherent configurations. This has given rise to some problems of terminology!

In 1973, Philippe Delsarte wrote a doctoral thesis at the Université Catholique de Louvain, which was reprinted in the Philips Research Reports Supplements, and has been one of the most influential documents in the theory. Delsarte restricted himself to commutative association schemes, though in fact most of his examples are symmetric. He observed that these provide a setting for two important areas of discrete mathematics: error-correcting codes and t-designs. Codes are easier to explain here.

An association scheme is P-polynomial if there is a relation matrix R1 in the scheme which generates it, in the sense that Ri is a polynomial of degree i in R1. The graph with edge set R1 is what is known as a distance-regular graph. An important class of examples are the Hamming graphs, where the vertex set is the set of all words of length n, or n-tuples over an alphabet of size q, two vertices being joined if they differ in just one coordinate.

A d-error-correcting code is a set of words with the property that, if one is transmitted through a noisy channel and at most d symbol errors occur, then the received word is still closer to the transmitted word than to any other word in the code; so, with this assumption, the transmitted word can be found. This is just a set of words (or vertices in the Hamming graph) whose pairwise distances are all at least 2d+1. Delsarte observed that this definition could be made for any distance-regular graph, and many of the results about such codes (including the sphere-packing bound and Lloyd’s Theorem) could be proved in the more general situation. (Norman Biggs was developing similar ideas at about the same time.) Delsarte also showed that the technique of linear programming could be used to find new bounds on codes which in some cases were stronger than any previously known.

Delsarte also remarked that there was a dual concept to P-polynomial schemes (or distance-regular graphs), which he called Q-polynomial schemes; and that these schemes provided a setting for a generalisation of t-designs (in the so-called Johnson schemes) and orthogonal arrays (in the Hamming schemes).

At about this time, Eiichi Bannai and Tatsuro Ito were using similar techniques to prove the non-existence of Moore graphs with diameter greater than 2 other than odd cycles. (These graphs, which I won’t define here, would be examples of distance-regular graphs. The theorem was also proved by Damerell at about the same time.)

This led, a few years later, to a very influential book on algebraic combinatorics by Bannai and Ito, Association Schemes, I. (Volume 2 never appeared.) These authors defined association schemes to be homogeneous coherent configurations; but, like Delsarte, most of the important examples were symmetric. Their focus was on schemes which are both P- and Q-polynomial. I mentioned above that in a P-polynomial scheme, the i relation matrix is a polynomial of degree i in the first one. These polynomials satisfy a three-term recurrence relation, and so form a family of orthogonal polynomials. For the Hamming scheme, these are the Krawtchouk polynomials; for the Johnson scheme, the Eberline or dual Hahn polynomials, as Delsarte had observed. Q-polynomial schemes give a dual family of polynomials. Some of the examples led to new families of orthogonal polynomials; one of these consists of the Bannai–Ito polynomials.

Of course I cannot trace everything that has happened since. In the preceding post, I described very briefly the talks given at the International Workshop on Bannai–Ito Theory in Hangzhou last month; as well as the subjects mentioned above, there were connections with synchronization, optimality, symmetric spaces, quantum probability, and much more.

I expect that much of this will be discussed at the Pilsen meeting. But in particular, one thing that will be under discussion is the history of the subject. Before all the participants have “left”, it is important to get a record of what happened in those confused early days, when communication between researchers was by letter, or (in the case of the Soviet Union and the West) virtually nonexistent.


About Peter Cameron

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

One Response to Symmetry vs Regularity

  1. This conference looks really interesting!

    This is a shameless plug, but with Martino Lupini and Laura Mancinska, we recently showed that you can define orbits on ordered pairs for a quantum permutation group, and these will form a coherent configuration just like in the classical case:

    The corresponding coherent algebra is then the centraliser of the magic unitary defining the quantum permutation group. I wonder if the degrees and multiplicities tell you anything about the quantum permutation group like in the classical case?

Leave a Reply

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

You are commenting using your 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