More graphs

NUS fish

John Bamberg is reporting on New Directions in Combinatorics on SymOmega (his report on Day 1 is here), so I will not even attempt to be comprehensive, but will just pick some plums.

Not very long ago, I reported the story of Graham Higman’s lecture to the LMS on his result that “the unknown Moore graph” on 3250 vertices could not be vertex-transitive. I had no idea what was about to happen …

Yesterday, Stefaan De Winter gave a talk on partial difference sets in abelian groups. He began with a result of Benson from 1970, giving a divisibility condition which is necessary for the existence of a certain kind of automorphism of a generalized quadrangle. He went on to mention extensions to partial geometries, partial quadrangles, and who knows what, before describing his own work, which applied this technique to partial difference sets in abelian group, leading to the nonexistence of all but two parameter sets on a list of “small” open cases. (The two remaining would each live in a group of order 216.)

But I am afraid I did not follow too closely, since I was sitting there slightly stunned. Benson’s formula included as a parameter the number a(g) of points p of the geometry for which p and its image under g are collinear.

Just such a formula, using just such a parameter, was at the heart of Higman’s proof, and was the reason why he could get further than Michael Aschbacher, who had proved that this unknown Moore graph couldn’t have a rank 3 group. (Careful analysis shows that there are two possible structures for an involution acting on such a graph; one was eliminated by Higman’s condition and the other is an odd permutation. The result follows easily from that.)

But the result is a special case of something more general. My first thought was, “Didn’t Norman Biggs prove that?” It may be that he did, I can’t at the moment find a reference. But I did find where to look for the general result. It, and Higman’s application, are on pages 89–91 of my book on Permutation Groups. The context is association schemes; here is a brief summary.

Automorphisms of association schemes

An association scheme is a collection of relations R1,…,Rr on an n-element set X with the properties

  • the relations partition X×X;
  • equality is one of the relations, say R1;
  • each relation is symmetric;
  • the span (over the real numbers) of the relation matrices A1,…,Ar is closed under multiplication.

It follows that the matrices in the fourth condition commute. Indeed, the second and third conditions can be weakened to say that the set of matrices is commutative and closed under transposition, and the complex numbers used in the fourth condition; this is a commutative coherent configuration, and everything below works equally well for this wider class.

The matrices are simultaneously diagonalisable, and so have r pairwise orthogonal common eigenspaces. Let E1,…Er be the orthogonal projections onto these eigenspaces. Then the Es form another basis for the span of the As. Let P be the change of basis matrix expressing the As in terms of the Es (its (i,j) entry is the jth eigenvalue of Ai), and Q the change of basis matrix in the other direction, expressing the Es in terms of the As.

Now an automorphism of the association scheme (in the strong sense, fixing all the relations) leaves the eigenspaces invariant, and so induces a linear map on each eigenspace. Thus the permutation representation of the automorphism group is decomposed into representations on these eigenspaces. It is easy to compute the character of the jth representation: its value on an automorphism g is a linear combination of the numbers ai(g), the number of points x for which (x,xg) satisfies the ith relation), and the coefficients are given by the entries of Q.

Once we have a formula for the character, various conditions can be deduced; these can all be regarded as necessary conditions for the existence of an association scheme with an automorphism of the appropriate type. For example,

  • Any character value is an algebraic integer (indeed, lies in a cyclotomic field), and so if rational it is an integer. Applying this to the identity automorphism gives the usual “integrality conditions” for the existence of an association scheme.
  • The inner product of characters, for example this character with the trivial character, or with itself, must be non-negative integers.

So Stefaan has added to to the stock of applications of this technique. Surely there must be many others?

A final question: does anyone have more information about the history of this technique? Did Benson invent it? (I have little doubt that Higman discovered it independently, but I don’t know the date; I think his lecture was in the late 1970s or early 1980s.)

About Peter Cameron

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

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.