Pilsen, days 1 and 2

Pilsen, Republic Square

The conference on “Symmetry vs Regularity” in Pilsen has begun.

I hesitate at trying to describe the talks, since the first day alone had 13 talks, and the second day 19, of lengths ranging from ten minutes to an hour, with no parallel sessions.

Random thoughts will have to suffice.

The meeting largely concerns the structures variously known as association schemes or coherent configurations. These had at least three independent origins: by R. C. Bose and his students and collaborators in experimental design in statistics; by Issai Schur in permutation group theory; and by Weisfeiler and Leman in studying the graph isomorphism problem (it is the fiftieth anniversary of their paper that we are specifically celebrating at this conference).

Subsequently the methods began to coalesce: Jaap Seidel recognised the connections between Bose’s and Higman’s work, and as communications between the Soviet Union and the west improved we were able to appreciate each other’s contribution. Delsarte applied Bose’s methods to coding theory and design theory, and Bannai and Ito wrote an important book laying out the essentials of the theory.

I began life in Schur’s school in this respect. As a beginning D.Phil student at Oxford, I was given by Peter Neumann his long preprint on extending Wielandt’s theorem on primitive groups of degree 2p (p prime) to degree 3p. Then Donald Higman visited Oxford and lectured on coherent configurations, perhaps his first complete presentation of the theory he had developed; one of the key ingredients, what we now sometimes call the “Bose–Mesner isomorphism” from the algebra generated by the basis matrices to the algebra generated by the intersection matrices, he attributes to Wielandt (see the Appendix of his 1967 paper on intersection matrices). Wielandt was a student of Schur and has much to say on “The method of Schur” and its connection with representation theory in his book on Finite Permutation Groups, which is dedicated to Schur.

Anyway, I was one of two students assigned to take notes of Higman’s lectures (the other was Susannah Howard); the notes, corrected by Higman, were published in the Mathematical Institute Lecture Notes series.

This leads me to the talk by Alexander Gavrilyuk on “Graham Higman’s method”. I bear some of the responsibility for this. Graham Higman gave a formula for the character of an automorphism group of an association scheme on one of its eigenspaces, in terms of (in Delsarte’s terminology) the Q-matrix of the scheme and the functions ai, where ai(g) is the number of points x such that the pair (x,xg) satisfies the ith relation of the scheme. He used this to show that the hypothetical Moore graph of valency 57 could not have a transitive automorphism group. Higman never published this (though he addressed the London Mathematical Sociey on it), but I thought it was potentially a useful technique and gave it as an example in my Permutation Groups book.

Meanwhile, C. T. Benson had used it to study automorphisms of generalised quadrangles and beyond, and later authors had extended this to other generalised polygons, perhaps without realising that it works for any association scheme. Two years ago in Singapore, Stefaan de Winter talked about applications of this, and I briefly discussed Higman’s work with him. Alexander did mention some more recent work; it seems people are on the case at last.

Another small observation. Walter Feit and Graham Higman proved their theorem by considering the collinearity graph of the generalised polygon (whose vertices are the points, adjacent if collinear); this graph is distance-transitive, so the association scheme is symmetric and commutative, and eigenvalues tell you everything. Donald Higman gave a new proof of the theorem using the coherent configuration based on flags of the geometry; this is non-commutative and one has to study the more difficult 2-dimensional representations, but the payoff is that one gets more refined information, including “Higman’s inequality” for generalised quadrangles. This approach fits better with the BN-pair structure in the group case.

My account of the Singapore meeting is here.

But there is a small historical mystery here. Did Benson get the idea from the Feit–Higman paper, as Alexander thought possible? (I have looked through the paper and I don’t think this is very likely.) Was there another connection? I am inclined to believe that the two inventions were completely independent. Perhaps it should be the Benson–Higman method?

In the evening there were four short talks. Two nice things for me. Bogdana Oliynyk talked about an extension of an old paper I wrote with Sam Tarzi about diagonal limits of cubes; she and her co-authors have extended it to Hamming spaces over arbitrary finite alphabets. Then Alicia Roca talked about invariant subspaces. There was some nice combinatorics in there, but a key paper included Bill Longstaff as an author, and this took me back. He was an undergraduate with me, and about 40 years ago I met up with him on a visit to Perth, where he told me some of this material. I think it was on the same visit that Cheryl Praeger and I proved the theorem about dual polar graphs that Sasha Ivanov mentioned in his talk opening the conference.

A highlight for me of the second morning was the talk of Oleg Verbitsky, who looked at the Weisfeiler–Leman algorithm from the viewpoint of logic. Success of the k-dimensional version corresponds to a formula in first-order logic with counting quantifiers which characterises the graph up to isomorphism, with k+1 variables; the quantifier depth determines the number of rounds required. This was explained with a very nice Ehrenfeucht game on the pair of graphs. The two players are provided with matching collections of coloured pebbles. The first player is trying to demonstrate non-isomorphism of the two graphs, and the second player to prevent this. The pebbles correspond to the variables in the formula, and the number of rounds of the game to the quantifier depth.

The highlight of the afternoon was the talk by John Wilmes. He was a student of Laci Babai, and he and Xiaorui Sun took the first step since 1980 towards a conjecture of Babai. Back then, Babai proved that primitive but not 2-transitive permutation groups had order bounded by exp(n1/2) (this is slightly inaccurate, since we might have to put some log n factors in the exponent; I will be similarly cavalier throughout this comment). This is best possible, since both the symmetric group acting on 2-sets, and the automorphism group of the square lattice, are primitive groups with order about this value. Indeed Babai’s bound and reality differ by a constant and a single log factor in th exponent.) But actually Babai proved much more; his bound applies to the automorphism group of any non-trivial coherent configuration.

About the same time, the Classification of Finite Simple Groups was announced, and using this, Babai’s result for groups could be deduced. Indeed, much stronger results can be proved; with “known” exceptions (essentially powers of the symmetric or alternating group acting on k-sets, wich some group permuting the coordinates), the orders of primitive groups don’t exceed nlog n+1. Babai conjectured that with a similar list of exceptions, the order of the automorphism group of a primitive coherent configuration could not exceed exp(nε) for some arbitrarily small ε. His theorem gave ε = 1/2; and, of course, CFSG is no help here, except perhaps as a guiding principle.

Now Sun and Wilmes have reduced this to ε = 1/3. So, in particular, they have to deal with the two examples with very large automorphism groups, which they do by building “clique geometries” for them, which turn out to be the partial geometries in the sense of Bose (who was perhaps the first to use geometric arguments on cliques to characterise strongly regular graphs). It is a beautiful combinatorial argument; but here I will only say, you should have been there! It was also a beautifully planned and executed talk, with just the amount of detail that could be comfortably fitted into the time allowed.

One thing from the evening session: Mikhail Kagan was using resistance distance as an alternative to the Weisfeiler–Leman algorithm. This is something I have an interest in, as it connects (among other things) with statistical optimality. I would like to see the result of resistance distance applied to the collaboration graph!


About Peter Cameron

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

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 )

Google+ photo

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