Pilsen, days 5 and 6


So the conference is over; but before I start a description of the last two days, let me pose a problem which might be an interesting small research topic for someone.

As I have said, statisticians love symmetric real matrices. Indeed, some of them love these so much that they tinker with matrix multiplication to preserve symmetry. The Jordan product of two square matrices of the same size is given by A*B = (AB+BA)/2. Thus, the Jordan product of symmetric matrices is symmetric.

Some time ago I defined the notion of a Jordan scheme, the analogue of a coherent configuration for the Jordan product. It can be defined in terms of a partition of Ω2 into subsets, but I will give the simpler definition in terms of matrices. A Jordan scheme is a set of square zero-one matries of the same size, satisfying the conditions

  • the sum of all the matrices is the all-1 matrix J;
  • there is a subset of the matrices whose sum is the identity matrix;
  • all the matrices are symmetric;
  • the real linear span of the matrices is closed under Jordan product.

It is clear that the symmetrisation of a coherent configuration (obtained by adding each non-symmetric matrix in the configuration to its transpose) is a Jordan scheme. I made a conjecture, which seems to me a bit unlikely: every Jordan scheme is the symmetrization of a coherent configuration.

I never spent any time on this conjecture, apart from failing to find any easy counterexamples. To investigate it, it would be useful to have a tool. So here I propose a tool: symmetric Weisfeiler–Leman algorithm. In other words, modify the usual Weisfeiler–Leman algorithm (which you can find defined in several slides from the conference, for example those of Sven Reichard or Oleg Verbitsky) so that it deals only with symmetric relations; so, when considering a pair (x,y), it counts the paths of a given type from x to y and those of the same type from y to x.

I assume that no implementation of this has ever been produced, so I may have to write my own. But it would be a valuable tool in exploring the conjecture, and raises a question in its own right:

  • is it the case that the configuration produced by symmetric WL is the symmetrisation of the configuration produced by WL?

I can’t see a good reason why this should be so, but if it were, one could pick random configurations and apply ordinary and symmetric WL to them and check whether the latter was the symmetrisation of the former.

I mentioned this to Pascal Schweitzer, and he agreed that all the above questions almost certainly have a negative answer. This is a good thing, since there is potentially a theory of Jordan schemes which is not just about symmetrised coherent configurations.

Anyway, I had written the above before the final day’s lectures. I was amazed when Sergey Shpectorov, in a beautiful talk about successive generalisations of the Griess algebra for the Monster to the present concept of axial algebras (more on this shortly), mentioned Jordan algebras. More evidence that there is an interesting theory lurking here!

Now a couple of comments on things I said earlier. Alexander Gavrilyuk wasn’t convinced by my comments on Higman and Benson, and showed me the abstract of Benson’s paper where he specifically credits Feit and Higman for the idea. I will do more research on this, read the papers, and write a longer report. I don’t know yet what its conclusion will be – any bets? Also, István Estélyi, a local, told me that it is not correct that brewing is the only industry in Pilsen. Although Škoda cars are no longer made here, trams and trains are manufactured. Indeed, on Saturday morning, smoking chimneys were clearly visible from the hotel terrace.

Anyway, back to business. The first talk on Friday was by Laci Babai. His title was the same as the conference title, “Symmetry vs Regularity”, and indeed Laci has done more than anyone else in the last fifty years to explore this distinction. Although symmetry implies combinatorial regularity, and one might naively expect a converse to hold, Laci contends that in most cases regularity is the enemy of symmetry; one can bound the number of automorphisms of regular objects like coherent configurations, with known exceptions. [There is one situation which doesn’t fit the paradigm. Sometimes, strong regularity conditions imply symmetry, because actually they imply a complete characterisation, and the only objects which satisfy the conditions are symmetric ones. I will come back to this later.] In one of his later talks, which were “tutorials” on his quasi-polynomial algorithm for graph isomorphism, he drew the moral that “the opposite of hidden irrecularity is not hidden regularity, but hidden robust symmetry.” This was in the context of his “split-or-Johnson” subroutine. The general structure of the algorithm is to break enough symmetry that one can apply Luks’ “divide-and-conquer” methods. You cannot easily divide Johnson graphs. Fortunately, with Laci’s device of an “ideal set”, Johnson graphs allow you to reduce very greatly the size of the sets you need to consider.

More diversions in that paragraph than good writing rules might allow; but there were so many connections! Anyway, Laci proposed two conjectures for “group theory without groups”:

  • There is a function f such that a primitive coherent configuration with a non-trivial subdegree d has all subdegrees bounded by f(d). (In the group case, this is Sims’ Conjecture, an early consequence of CFSG. For distance-regular graphs, it is the Bannai–Ito conjecture, now proved.)
  • With “standard” exceptions, the order of the automorphism group of a strongly regular graph on n vertices is at most polylogarithmic. (The standard examples are disjoint unions of complete graphs of the same size, line graphs of complete and complete bipartite graphs, and complements of these.) (A stronger form of this bound, with more exceptions, holds for all primitive permutation groups, another consequence of CFSG.)

Back to symmetry vs regularity, I proposed the following example, which seems to lie right on the borderline. Desargues’ Theorem is a regularity condition for projective planes; at first it seems to support Laci’s argument, since it is strong enough to imply a classification (such a plane is coordinatised by a skew field). But looking a bit deeper, Desargues’ Theorem immediately implies the existence of many automorphisms, namely central collineations (at least n5/2, if n is the number of points of the plane). It is these central collineations which are used to classify the planes, since the addition and multiplication groups of the field are groups of central collineations with fixed centre and axis.

Laci had explained his results on the connections between minimal degree, thickness, and (in some cases) order of automorphism groups of coherent configurations. The next talk was by his student Bohdan Kivva, who had proved Ω(n) lower bounds for the minimal degree of the automorphism groups of distance-reguar graphs of fixed diameter and of primitive rank 4 coherent configurations; a tour de force using combinatorial and spectral methods as well as characterisations in special cases.

Tatsuro Ito gave an update on the progress of the classification of (P&Q)-polynomial association schemes; he surveyed the known examples, described Leonard pairs and the work of Terwilliger, and left us the impression that progress continues to be made but the end is not yet.

Then we had an introduction to quantum permutation groups by David Roberson, where permutation matrices are replaced by “magic unitaries” over a C*-algebra. The good news for classicists is that these give rise to coherent configurations in the sense we already know.

Pascal Schweitzer gave a very interesting talk about the Weisfeiler–Leman algorithm. In particular, he mentioned that planar graphs have WL-dimension at most 3, using Tutte’s “spring embedder” of a planar graph (you replace edges by springs, and let the configuration move to a lowest energy state). He also has a complete characterisation of graphs identified by 1-dimensional WL.

The day ended with a short presentation by Sasha Ivanov. He pointed out that there are geometries for M24 (octads–trios–sextets) and L5(2) (the projective geometry) with many local symmetries: the point, line, and point-line stabilisers are isomorphic, although the embedding of the last in the other two is slightly different in the two cases. So the groups are homomorphic images of slightly different amalgamated products. I must admit I was left a little unsure of what exactly the point was; he wasn’t announcing that he had glued the two pictures together to get a new simple group (at least I don’t think so). Right at the end it appeared that he was advertising his new book.

We had a half-day on Saturday morning to finish the conference by lunchtime. This made, by my count, a total of 64 talks in four full and two half days; unsurprisingly we were all tired! But most people were still there at the end, a remarkable testimony to the success of the meeting. The highlight of the morning, for me, was a pair of talks by Sergey Shpectorov and Madeleine Whybrow on axial algebras, which are (as I mentioned) the current endpoint of a line of generalisation starting with the Griess algebra and going on to work of Sakuma, Ivanov, Pasechnik, Seress and Shpectorov. In the original case and the first version considered by Sasha (Majorana algebras), the distinguished idempotents have eigenvalues 0, 1, 1/4 and 1/32. (If you are wondering how an idempotent can have eigenvalues other than 0 and 1, remember that these algebras are non-associative!). Also there are fusion rules implying that there is a C2 grading, where the 1/32–eigenspace has degree −1 and the others +1. Now one can vary both the numerical values of the eigenvalues and the fusion rules and see what you get.

The C2 grading implies that the “reflection” negating the elements of degree −1 is an automorphism of order 2; these automorphisms have the property that their pairwise products have order at most 6, so form a normal set of 6-transpositions in the group they generate. Now group theory tells us where to look for examples. (Another case where regularity implies symmetry.) Madeleine, with Markus Pfeiffer in St Andrews, is producing GAP programs to allow the user to play with these fascinating objects.

Roman Nedela asked me to say a few words to close the conference. My main message was that “Symmetry vs Regularity” is not like a football game where someone loses and is eliminated; it is more like a cooperative game. Laci Babai uses group theory to indicate what might be true and where the interesting examples are, before developing techniques to prove things without group theory (and thus get much stronger results).


About Peter Cameron

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

2 Responses to Pilsen, days 5 and 6

  1. Michel Marcus says:

    sorry, small typo: symmtrised

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.