G2D2, 2: first week


The campus of the China Three Gorges Hotel has a small river, full of waterlilies and lotus flowers. Beside it runs a main road, along which big water trucks run, shooting atomised water from cannon-like structures; we are told this is to reduce the air pollution.

After an introductory party on Monday, the conference opened at 9:00 on Tuesday morning. In the first week, much of the activity is minicourses 1 and 2, the first on “Laplacian eigenvalues and optimality” given by Rosemary and me, the second on “Topics in representation theory” by Tullio Ceccherini-Silberstein.

But first, some words on the two logos, which appear at the top of the first post in this sequence.

The meeting is being held in the Three Gorges Mathematics Research Centre, whose logo is on the right. It is part of the China Three Gorges University, near the famous Three Gorges on the Yangtse River. The University’s logo, which I am sure your search engine will quickly find, features three vertical wavy shapes, which presumably are intended to suggest water cascading through the three gorges. The TGMRC logo cleverly replaces these random shapes by integral signs, which they somewhat resemble.

The TGMRC is on a corridor on the top floor of a U-shaped building called L1 or L2, depending on which side you enter. The top of the U is closed by a high bridge. So it somewhat resembles the new location of the ICMS in Edinburgh, except that that building is entirely enclosed, whereas the central courtyard of L1/L2 is open to sun and rain. There is a nice lecture room with comfortable chairs. Although there is no public space except for the corridor (where the welcome party was held), there are a number of rooms which can be used as “breakout rooms” for small discussions.

The conference logo on the left is a Deza graph. There has been a recent upsurge of activity on Deza graphs, which I suspect is driven by Sergey Goryainov.

A Deza graph is a regular connected graph for which the number of common neighbours of two vertices takes just two distinct values. If adjacent vertices have one number of common neighbours and non-adjacent vertices the other, then the graph is strongly regular. So a strictly Deza graph is defined to be a Deza graph of diameter 2 which is not strongly regular. The graph in the G2D2 logo is the smallest strictly Deza graph, as you can easily verify. I do not know whether the colours have any mathematical significance.

On Wednesday, Dmitry Panasenko told us about a clever computer search which found all the strictly Deza graphs on up to 21 vertices. For one parameter set (I think on 20 vertices) there are many non-isomorphic graphs (I think around 20 or 30, though I didn’t copy down the number from a long table). Then Soesoe Zaw told us about some new constructions of strictly Deza graphs from the Berlekamp–van Lint–Seidel graph, using the operation of dual Seidel switching due to Willem Haemers. This pleases me, since I am typing this on a computer called Seidel.

The Berlekamp–van Lint–Seidel graph is a graph on 243 vertices which is dual (in the sense of Delsarte duality for association schemes) to the graph associated with the perfect ternary Golay code C of dimension 5 over the field of 3 elements. Take the dual code of C (which is 6-dimensional of length 11 and contains C as a subcode of codimension 1). The vertices of the graph are the cosets of this dual code; two vertices are joined if their difference contains a word of weight 1. It is a “sporadic” strongly regular graph with 243 vertices, and from it Soesoe was able to construct a strictly Deza graph on 243 vertices and two of them on 486 vertices.

Seidel’s name came up again in Wei-Hsuan Yu’s talk on equiangular lines, in which he began with the results which I saw from close-up in the early 1970s by Lemmens, Seidel, Higman, Taylor, Gerzon, and so on, and then gave some improvements, some of which have been obtained by semi-definite programming; and again in Alexander Gavrilyuk’s talk on digraphs whose Hermitian adjacency matrices have spectral radius at most 2.

One of the invited speakers was Gareth Jones. He was going to tell us about his recent theorem that many triangle groups contain uncountably many maximal nonparabolic subgroups (subgroups maximal with respect to containing no parabolic elements in their action on the hyperbolic plane). But for reasons not revealed, he was unable to come to the meeting. Instead, Alexander Mednykh had offered to give a talk to Gareth’s slides. Very brave, I thought. But Sasha began by explaining to us the basic idea behind the proof, a mix of maps and hypermaps, coverings, Riemann surfaces, etc.

Qing Xiang gave us new bounds for the size of a partial ovoid in either the generalised quadrangle E(5,q) (what I might call Ω(6,q) and in the Ree–Tits generalised octagon; in each case, previous bounds were of order a power of q, but he and his co-authors have managed to lower the exponent of the power. He showed us Chris Godsil’s nice proof of Jef Thas’ q3q2+q bound in the GQ case, based on association scheme techniques (and so potentially useable in much more general situations). The new bound uses modulo p techniques and very specific results about dimensions of modules for algebraic groups, and while much more powerful in this case is likely to be much more specialised.

There have been several mentions of Cayley graphs, and I must point out a notational trap. Given a subset S of a group G, not containing the identity, the Cayley (di)graph Cay(G,S) is the graph with vertex set G and with an arc from x to sx for every s in S. If S is inverse-closed, it is an undirected graph. It admits the action of G on itself by right multiplication (the right regular action) as automorphisms. In fact, any graph which admits G acting regularly as a group of automorphisms is necessarily a Cayley graph for G.

Now there are two, quite different, definitions of a normal Cayley graph:

  • The definition I learned first says that Cay(G,S) is a normal Cayley graph if S is a normal subset of G (closed under conjugation by elements of G); equivalently, the graph admits both the left and the right regular action of G as automorphisms.
  • The definition which seems to be standard among participants at this conference is: Cay(G,S) is a normal Cayley graph if G is a normal subgroup of the full automorphism group of the graph.

The first definition is very restrictive but also very useful. For two examples,

  • A graph invariant under the primitive group of simple diagonal type whose socle is the product of two copies of the simple group T is a normal Cayley graph for T.
  • For n > 3, Henson’s universal homogeneous Kn-free graph is not a normal Cayley graph for any group (though Greg Cherlin showed that it is a Cayley graph).

The second definition, by contrast, says essentially that a normal Cayley graph has no “unexpected” automorphisms: its automorphism group is contained in the holomorph of G. In accordance with the principle that graphs tend to have few automorphisms other than those you must have, we would expect that most Cayley graphs are normal; this has indeed been conjectured, with some evidence.

I wish that we had different words for these two obviously useful concepts. But it is probably too late for that now; one of them will just fade away.

The paragraph two above reminds me of an old theorem of mine, the citation for which was just imported from Scopus into the St Andrews research repository. For every finite group G, there is a constant α(G), between 0 and 1, so that, in the class of n-vertex graphs whose automorphism group contains a subgroup isomorphic to G, the proportion whose automorphism group is exactly G tends to the limit α(G) as n→∞. In accordance with the above principle, you might expect that most groups have α(G) = 1; but in fact this happens if and only if G is a direct product of symmetric groups, and the values of α are dense in the unit interval.

The idea of terminology fading away came up in Misha Muzychuk’s nice survey of coherent configurations for the summer school. As I have probably pointed out here before, at the end of the 1960s, within a couple of years of each other, Donald Higman invented coherent configurations, while Weisfeiler and Leman invented cellular algebras. The latter notation has faded away, partly because the term has been re-used with an entirely different meaning. But long before this, Bose and Nair invented association schemes, which are an important special case of coherent configurations. There are four levels of generality; in increasing generality, a coherent configuration may be symmetric, commutative, homogeneous, or none of the above. Bose and Nair used the term “association scheme” for symmetric c.c.; Delsarte used it for commutative c.c.; Bannai and Ito used it for homogeneous c.c., and this seems to have become standard. I prefer to use the term “coherent configuration” with appropriate qualification.

Unfortunately Misha did not have time to describe his recent construction, with Klin and Reichard, of proper Jordan schemes; but Mike Kagan will talk later in the meeting, and I think he might say something about this.

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.

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 )

Connecting to %s

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