Pilsen, days 3 and 4

After the rush of the first two days, things quietened down a bit, so I can stop and look around me.

The conference logo, and an explanation, is here. Norman Biggs, one of the pioneers of algebraic graph theory, speculated that perhaps for any feasible parameters for which a mathematical object exists, there would be at least one highly symmetric object with those parameters. This speculation was debunked when the strongly regular graphs on 26 vertices were classified; none of them is vertex-transitive. The particular one used for the logo, still has quite a lot of symmetry; its group is A₅×C₂, with two orbits on vertices, of lengths 6 and 20, which can be interpreted in the icosahedron.

Pilsen is a former industrial town which was populated by Czechs, Germans, and Jews. Because of events surrounding the second world war, the second and third of these peoples have largely gone, and there is not too much industry here apart from beer production. (How many other towns have given their names to a type of beer?) But some fine old buildings remain.

One of these is the town hall; the conference takes place in the Council chambers on the top floor of this building. (The picture in the last post was taken through the windows of this room.) The desks all have microphones which can be activated at the press of a button. We are supposed to use these when asking a question of a plenary speakers, since these are recorded (and will hopefully be made available at some point). But we are not always so disciplined …

On Wednesday we had talks in the morning (only six; it seemed like a holiday), and excursions in the afternoon. The most interesting talk of the morning was the plenary by Edwin van Dam. He explained to us what semidefinite programming is, how it can be used to find bounds for the Max-cut problem, with applications to chromatic number, bandwidth, and other problems. Very relevant to the conference, he showed us how the fact that the relevant matrices lie in an algebra of relatively low dimension can be used to reduce very substantially the amount of computation required to use the method: this applies to graphs in a coherent configuration, graphs with a lot of symmetry, and walk-regular graphs. I suspect that there are techniques here useful for the synchronization project, but not a lot of time to think it through now.

Elena Konstantinova talked about a nice topic, integral graphs (those all of whose eigenvalues are integers). After a historical introduction, she turned to Cayley graphs. Towards the end of the lecture, she mentioned that Problem 19.50(a) of the Kourovka Notebook, which asks whether the Cayley graph of a group G with respect to a normal (conjugation-closed) set of involutions is integral, has a positive solution, produced independently by D. O. Revin and A. Abdollahi, using character theory. She concentrated mainly on the star graph, the Cayley graph of the symmtric group S_n with respect to the set of all transpositions (1,i), for 2 ≤ i ≤ n. This graph is integral, and its eigenvalues and multiplicities are known. More details on this graph were given in the next talk, by Sergey Goryainov.

Thursday was entirely devoted to historical talks or reminiscences. This entire day had been arranged by Misha Klin, whose birthday it was; he had invited the speakers and even allocated topics to them.

The talks were extremely interesting. Some of the pioneers of the subject, such as Boris Weisfeiler, Dale Mesner, and Jaap Seidel, came to life at the hands of the speakers. Other talks traced the varied history of algebraic combinatorics from its roots in the work of Issai Schur and R. C. Bose, the various people who contributed to bringing the strands together (Seidel, Philippe Delsarte), and the strong direction provided by the book of Bannai and Ito.

We also heard about the great difficulties faced by members of the Soviet school pre-1990. The fact that many of them are now scattered all over the world illustrates what happens when governments treat their citizens like that.

But I won’t even attempt to summarise any of these talks. I hope that the slides (and perhaps even videos) will be on the web soon. I will announce this when it happens.

The day had been hot, and in the final session a thunderstorm hit and the rain came pelting down. It eased up just long enough to have the conference photograph taken before setting in again, leaving us the problem of getting to the dinner (in the Pilsner Urquell brewery) in the rain.