G2D2, 5: The logo revisited

There has been further discussion of the G2 logo; here is a brief summary.

Elena Konstantinova tells me that it was designed by Vava Stefoglo; her portfolio is here. She is not a mathematician but received a good education in mathematics. She designed the logo to look like a faceted diamond.

Misha Klin told us about a survey paper he wrote with Christoph and Gerta Rücker and Gottfried Tinhofer on algebraic combinatorics in mathematical chemistry, published in Match (the journal of mathematical chemistry), volume 40 (1999), 7–138; you can find it here. The particular graph used in the logo (a circulant of order 8) is discussed, along with other circulants of order 8), in Example 8.16 on pages 99–100, but you might have to read quite a bit of the preceding material to see what is going on.

As I noted, it is an example of a Deza graph. It was discussed at previous G2 conferences, by Sergey Goryainov, Stefan Gyurki, Anton Betten and Yinfeng Zhu at G2R2, and by Sergei Lando at G2C2.

Posted in events | Tagged , | Leave a comment

Random walks

Lots of mathematicians study random walks.

Diamond Geezer did one, indeed did two, with the same starting point and the same rules.

Posted in Uncategorized | Tagged , | Leave a comment

G2D2, 4: the second week

Kingfisher at CTGU

The lecturers of the first two minicourses now gave way for the second team.

Mike Boyle and Scott Schmieding told us about symbolic dynamics, in particular, subshifts and their automorphism groups. This was particularly valuable to me: I had dove into this subject without really knowing any of the background, so this was ideal for getting me up to speed. Collin Bleak, Jim Belk, Shayo Olukoya and I are developing an approach based on strongly synchronizing automata, so it was good to get a panoramic view of this particular landscape. Mike gave us an introduction, and Scott told us how algebraic K-theory (stable linear algebra over a ring) is relevant to the topic.

The other course was by Nobuaki Obata, on spectra of graphs, where the graphs are either infinite or large finite. He took a quantum probability approach to this topic. I gained quite a lot of insights from this. In particular, I learned that three things I knew about were essentially different views of the same thing. As a student, I had learned about creation, annihilation and conservation operators, and never really understood them. In applied analysis I learned about the three-term recurrence relations used for calculating orthogonal polynomials. And in the theory of distance-regular graphs, there is the tridiagonal array of intersection numbers pioneered by Norman Biggs.

Another insight came from a very nice talk by Alexander Mednykh, who is able to do impressive computations of the number of spanning trees in various graphs. This number is the order of a group, the Jacobian group of the graph, a kind of homology group. His methods worked particularly well in the case of circulant graphs or cyclic coverings of graphs. The Chebychev polynomials play an important role here, and I now better understand why.

These polynomials are usually defined by the rule that Tn(cos x) = cos nx. Well, of course, trigonometric functions have to do with circles, and so might appear in studying circulant graphs … But there is a much stronger connection. An alternative specification of the polynomials is Tn(½(x+x−1)) = ½(xn+x−n). Now if x represents the adjacency matrix of a directed cycle, then x+x−1 represents an undirected cycle or Cay(Cm,{1,−1}), and then xn+x−n represents Cay(Cm,{n,−n}). The proof of the identity is straightforward; the usual definition shows that it is valid for all points on the unit circle, and hence since both sides are polynomials it is true in general.

The name of Jaap Seidel was mentioned a few more times; Jack Koolen dedicated his talk to Jaap. But another pioneer of spectral graph theory, Alan Hoffman, also featured several times, in particular in a beautiful talk by Akihiro Munemasa on Hoffman’s limit theorem. He extended it to Hermitian adjacency matrices of digraphs, and was able to take advantage of subsequent developments, in particular the root system interpretation of graphs with least eigenvalue −2, to give the proof.

As anticipated, Mike Kagan talked about resistance distance and the resistance distance transform as a tool for graph isomorphism, and its relationship to association schemes and Jordan schemes. Mike’s approach, coming from physics, is a bit different from mine, so there was plenty for me to learn, and the talk sparked several interesting unsolved problems in my mind. I might talk about some of these, if we make any progress on them.

Shiping Liu gave a talk that sparked my interest. There is a definition of “spherical graphs”, which captures and generalises the hypercube graphs. He was interested in discrete analogues of Ricci curvature and Cheng’s maximal diameter theorem. But I was reminded of dual polar spaces, which are a different generalisation of hypercubes. Is there a notion of “q-spherical graphs” which would capture these beautiful objects?

After the conference was over, several participants went to Shanghai for the minisymposium on dynamical systems; Rosemary and I went back to Hangzhou, where it was her turn to give a short course, on relations among partitions, posing a number of open questions about beautiful designs and arrays of various kinds such as triple arrays and multistage Youden rectangles.

Posted in events, exposition | Tagged , , , , , , , | Leave a comment

G2D2, 3: excursions

Yaokun Wu wrote me about the China Three Gorges University logo:

CTGU logo

Another understanding of the logo of TGU is some sailing boats and books, meaning sailing in the sea (river) of books.

As evidence for this, here is a picture of Three Gorges, presumably as it was before the dam was built:

Three Gorges

You can see that the sails of the boats in the foreground do resemble the CTGU logo. And here is the real thing:

Boats in Three Gorges

The last picture was taken on the conference excursion, which took us to several beauty spots on the Xiling Gorge, below the dam. I should probably say that “beauty spots” might be more accurately translated as “tourist spots”: the number of tourists is so great that, rather than allow them to ramble as they choose through the rugged and dangerous terrain, they concentrate them in a few places where suitable entertainment can be provided. The boats are at Longjin, where they feature in a story which was never quite clear to me, something about a girl being married off against her will, I think.

On a walk up the small side stream to a waterfall, I passed a sign which said, “”Watch your head observe and pass”. This sounds to me like an advanced meditation technique, but it was really a warning about an overhanging rock.

We also visited a reconstructed village of the Ba people, prehistoric inhabitants of the region. This time the story was even less clear to me; the musical accompaniment was pleasant enough, but the music played before the performance was much too loud and mechanical to be listenable. The audience sat on benches under three large and ancient trees; pleasant on a very hot day until I observed that every leaf on the trees was made of plastic.

The scenery was spectacular, but unfortunately the muddy water of the river and the polluted air made it impossible to take any pictures worthy of a tourist brochure. This will have to suffice:


The conference organisers, who delighted in satisfying our every desire, put on another ad hoc excursion at the end of the meeting, a half-day trip involving a visit to the famous dam followed by a cruise down the river. Here is a picture of the dam, the largest in the world, and some of the spectacular scenery we saw from the boat.

Three Gorges dam and Xiling Gorge

Posted in geography, history | Tagged , | Leave a comment

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.

Posted in events, exposition | Tagged , , , , , | Leave a comment

G2D2, 1: setting the scene


I’m in Yichang, at the China Three Gorges University, for the conference and summer school G2D2 (“Groups and graphs, designs and dynamics”).

This is the sixth meeting in the series: the previous ones were

  1. G2C2: Groups and graphs, cycles and coverings, Novosibirsk, Russia
  2. G2A2: Groups and graphs, algorithms and automata, Ekaterinburg, Russia
  3. G2S2: Groups and graphs, spectra and symmetries, Novosibirsk, Russia
  4. G2M2: Groups and graphs, metrics and manifolds, Ekaterinburg, Russia
  5. G2R2: Groups and graphs, representations and relations, Novosibirsk, Russia

The event following this one will be G2G2: Groups and graphs, geometries and GAP, and will be in Rogla and Portorož, Slovenia, as a satellite meeting of the European Congress of Mathematics.

This sequence inevitably invites one to play alphabet games. I would like to say “Groups and graphs, symmetry and structure”, but we have already had G2S2 which included symmetries. So perhaps I will say “G2I2: Groups and graphs, incidence and independence”. Perhaps “G2F2: Groups and Graphs, fields and functions” (or F2 could be the field with two elements).

The meetings are instructional workshops as well as conferences, and Rosemary and I are doing our double act on “Laplacian eigenvalues and optimality”, indeed we start off the meeting at 9am tomorrow morning.

Last week we were in the beautiful town of Hangzhou on West Lake, with its lotus blossoms at the peak of perfection, willow trees overhanging the water on which small boats plied, and pagodas standing above the trees.

West Lake

I gave a short course on “Four precious jewels”: you can find the slides on my St Andrews web page. (I have talked about this before but the short course gave the opportunity for a slightly longer presentation.) Yesterday we took the train from Hangzhou to Yichang, a seven-hour journey.

Things were in some doubt, as Hangzhou was battered by Typhoon Lekina, which brought heavy rain and strong winds over the previous two days; but the morning dawned fine and clear with hardly a breeze, and everything worked fine.

I hope to report on the meeting later, firewalls and slowness of response permitting.

Posted in exposition, history, Uncategorized | Tagged , , , , , , , , | 1 Comment

Some delay expected

In a few hours I will start out on a month-long trip to China.

I am not sure whether I will have the opportunity to post anything new or deal with incoming comments during that time. The Chinese disable several of my crucial work tools.

So please, if you don’t hear anything for a while, just be patient.

Posted in Uncategorized | Leave a comment