BCC at Birmingham, days 1-3

This week I am in Birmingham for the British Combinatorial Conference.

The organisation of the conference is outstanding. For one small example, yesterday, fifteen minutes before the Business Meeting was due to start, the Chairman noticed that we didn’t have the minutes of the previous Business Meeting to approve. The Secretary had the file on a laptop, and before the meeting started we had fifty printed copies to distribute.

After the excitement about ADE last week, these diagrams reappeared twice in the first couple of days, Hendrik Van Maldeghem (who talked about geometrical and combinatorial constructions of buildings) showed us all the crystallographic Coxeter–Dynkin diagrams. In a completely different context, Alexander Gavrilyuk mentioned the fact that connected simple graphs with spectral radius at most 2 are the ADE diagrams and the extended ADE diagrams. He attributed this to Smith (1969) and Lemmens and Seidel (1973). I think it would be not unjust to say that this result was part of the classification of the complex simple Lie algebras by Cartan and Killing in the last decade of the nineteenth century. That aside, Alexander was extending this to directed graphs, using a Hermitian adjacency matrix with entries 1 if there are arcs both ways between two vertices, while single arcs from v to w have i (the complex fourth root of 1) in position (v,w) and −i in position (w,v). This had been done by Guo and Mohar, but some small corrections were necessary; he used results of Greaves and McKee to achieve these. (As a footnote to this, it seems to be that to use τ, a complex 6th root of unity, in place of i would be more natural, since the sum of τ and its complex conjugate is 1 rather than 0.)

In fact, for the graph case, much more is known: the graphs whose greatest eigenvalue is at most 2 are the ADE diagrams and their extensions, but the graphs whose least eigenvalue is at least −2 can also be described.

The conference featured mini-symposia, and I organised one on “Designs and Finite Geometries”, which in my opinion has had some beautiful talks so far, from Ian Wanless on plexes in Latin squares, Rosemary Bailey on designs related to the Sylvester graphs (and the wrong turnings on the way to finding them), Peter Keevash on his and others’ results on existence of designs (including the fact that estimates for the number of Steiner systems, asymptotic in the logarithm, are now available, and hinting that he had constructions of large sets of Steiner systems for large admissible orders), and Moura Paterson on authentication schemes.

One of the most exciting talks was by Igor Pak. He has formulae, and good asymptotic estimates, for the numbers of standard Young tableaux for various skew Young diagrams. This was a mix of all kinds of things, including counting linear extensions of posets, rhombus tilings, plane partitions, counting disjoint paths, Vershik’s limiting tableau shapes, and a remarkable formula of Coxeter, which (if I copied it correctly) says

Σ(φn/n2) cos(2πn/5)  =  π2/100

(the sum over all positive integers n.)

Coxeter’s discovery of this formula was based on the existence of the 600-cell (a regular polytope in 4 dimensions) and some spherical geometry. As far as I can tell, the formula was not actually used in the talk, but the philosophy of it led to some of the things that came later.

Two things about the talk were a pity. First, there was no paper in the Proceedings. (In the history of the BCC, it has happened a few times that a speaker provided no talk; indeed I was the editor of the first “published-in-advance” volume, at Royal Holloway in 1975, where I failed to get papers from either Conway or Kasteleyn.) So I am unable to check these details. Second, Igor started in a bit of a rush, and some things were not clearly explained. For example, I think some nodding acquaintance with Plancherel measure is needed to make sense of the Vershik asympotic shape of a random Young diagram, and I didn’t find that in the talk. But it was so full of amazing stuff that it is perhaps churlish to complain.

Apart from these I will be very selective in my reporting. One contributed talk I really enjoyed was by Natasha Dobrinen, on the Ramsey theory of Henson’s homogeneous Kn-free graphs, which included a description of them in terms of trees. It went part rather fast (the talks were only 20 minutes), but I wonder whether this leads to a probabilistic approach to Henson’s graph. I have reported before how I laboured over this, and how Anatoly Vershik explained to me his construction with Petrov in a leisurely afternoon in Penderel’s Oak in London – a construction which is clearly related to the topic of graphons, the subject of Dan Král’s talk.

Then there was a sequence of three nice talks on quite different topics, but all related to permutations (in the combinatorial rather than the group-theoretic sense). Simon Blackburn proved a nice asymptotic result about random permutations for the uniform measure. At the end, Robert Johnson asked whether there were similar results for other measures. This was because Robert’s talk, which was next, was able to prove some of the results for wider classes of measures, though not for the Boltzmann measure, which he gave as an open problem. Then David Galvin talked. One of his results was that, far from being monotonic, the sequence of coefficients (excluding the constant term) in the independent set polynomial of a graph with independence number m can be any permutation of {1,…m}. This suggested to me another interesting measure on permutations. Choose n much larger than m, and choose a random graph on n vertices with independence number m; this induces a probability measure on the permutations. Does this measure tend to a limit as n→∞? If so, this could claim to be a “natural” measure on permutations. Fred thought this was an interesting question.

Any ideas?

We had a reception in the remarkable Barber Institute of Fine Arts. Guided tours of the gallery were offered. We went upstairs, and the first picture we saw was René Magritte’s famous picture “The flavour of tears”. Tuesday was the concert, and apart from having to move to a different room because the piano hadn’t been unlocked, we had a remarkable evening’s entertainment; there are several outstanding pianists at the conference. Today is the excursion, to the Museum of Black Country Living; but I have work to do …

Posted in events | Tagged , , , , , | 1 Comment

Aliens Do Exist

The people from the planet Ade have intercepted radio transmissions from Earth, and have discovered that we know about the Petersen graph

Petersen graph

and the root system E6.

One day, a flying saucer from Ade arrives on Earth and delivers an ultimatum:

Either show me a construction of E6 from the Petersen graph, or I will arrange that Boris Johnson will be the next Prime Minister of the United Kingdom.

Too late, I present the solution the alien is looking for.

In the usual representation of E6, the roots all have length √2, and have inner products in the set {2,1,0,−1,−2}. Clearly inner product 2 means the roots are equal and inner product −2 means that one is the negative of the other. So there are three “non-trivial” values for the inner product. But a graph has only two relations, adjacency and non-adjacency; so I will look for a set of 10 vectors with all inner products 0 and 1, with 1 for adjacency and 0 for non-adjacency in the Petersen graph.

The outer pentagon is easy to deal with. Take five basis vectors e1, …, e5 for R5. Then the vectors e1+e2, e2+e3, …, e5+e1, will do the job: each has inner product 1 with its neighbours in the cycle and 0 with its non-neighbours.

To get the inner pentagram, the first step is to find five vectors, each having inner product 1 with one vector in the outer cycle and 0 with all the others. A bit of experimentation shows that (e1e2+e3e4+e5)/2 has inner product 1 with e5+e1 and 0 with the other four; the rest of the vertices can then be found by cyclic permutation.

But there is a problem: these vectors are too short; their lengths are only √5/2.

The solution is to add a sixth dimension and extend the vectors in this dimension. Take a new basis vector e6, and add ce6 to each of the five. To get length √2, we have to choose c = √3/2. This doesn’t affect inner products with the first five, since e6 is orthogonal to them.

Moreover, by a sort of miracle, we find that the inner product of one of these extended vectors with its neighbours in the cycle is 0, while its inner product with its non-neighbours is 1. This gives us the inner pentagram correctly, so the job is done.

But wait a minute, where is the root system? We have produced vectors of the right lengths, and having the right inner products. But a root system must be closed under reflection in the hyperplane perpendicular to each of its vectors. How to we achieve that?

The answer is simple: we simply close up. Take the reflection of the vectors we have in the hyperplanes perpendicular to each of them; this gives some new vectors. Repeat the procedure with the enlarged set until no new vectors are found. Then we have a root system. A little thought, or a little theory, shows that it is an indecomposable root system in R6 with all roots of the same length, and is not A6 or D6; so it must be E6.


I am writing this at the LMS-sponsored Undergraduate Summer School at the University of Leeds. This consists of several mathematicians giving short courses (three lectures and two tutorial sessions) on different branches of mathematics, and a few other people giving one-off talks (or in my case, two one-off talks). The students are very keen and engaged, and tackle the problems (including challenge questions) with great enthusiasm.

One of this week’s lecturers is Sira Gratz from the University of Glasgow, talking about what readers of this will recognise as one of my favourite topics: what I call the ADE affair. Sira entitled her series “Attractive Diagrams Everywhere”, which she has certainly demonstrated; she did admit in her first lecture that someone interpreted the acronym as “Aliens Do Exist”.

Her selection of topics was (to my great pleasure) almost disjoint from what I would have chosen myself: the three lectures described, in detail, root systems, quivers of finite representation type (Gabriel’s theorem shows that these must be orientations of ADE diagrams), and cluster algebras (Fomin and Zelevinsky showed that the finite-dimensional ones are also described by orientations of ADE diagrams). She explained in each case the wider significance of the ideas.

Anyway, tomorrow I am talking about the (countable) random graph. I had planned to start off with the Petersen graph, to point the contrast between finite and infinite. The Petersen graph is highly symmetric, but very atypical among finite graphs (random finite graphs have no non-trivial symmetry with high probability), whereas the countable random graph (there is only one) is highly symmetric.

But I thought it would be nice to make some connection with Sira’s lectures. Thinking about the Petersen graph and root systems led me to the construction I have just described.

Posted in doing mathematics, events | Tagged , , , , | 1 Comment

Proper Jordan schemes exist!

A new field of research has just been created by Misha Klin, Misha Muzychuk and Sven Reichard: proper Jordan schemes.

They answered a question which I posed some time ago (I don’t remember when), about whether such objects exist. I would not be interested in “empty set theory”, but now we know that they do exist, so we can go ahead and study them.

A little background. You can find more here or here (the second of these references gives some further reading).

Jordan algebras

A Jordan algebra is a vector space (here over the real numbers) with a multiplication ∗ satisfying

  • AB = BA;
  • (AB)∗(AA) = A∗(B∗(AA)).

These algebras were introduced by Pascual Jordan as a mathematical foundation for quantum mechanics. While they have not caught on for this purpose, they are used in some parts of statistics, especially for estimation of variance components.

Any associative algebra gives rise to a Jordan algebra, on setting AB = (AB+BA)/2. Certain subsets of matrix algebras are also closed under this product and define Jordan algebrasi. Most significantly, the symmetric matrices form a Jordan algebra. An important theorem, the Jordan–von Neumann–Wigner theorem, asserts that apart from some infinite families arising in this way, the only simpleJordan algebra is an exceptional 27-dimensional algebra related to the octonions and the Lie group E6.

Coherent configurations and Jordan schemes

A coherent configuration is a set C of zero-one matrices satisfying

  • the sum of the matrices in C is the all-one matrix J;
  • the identity is the sum of some of the matrices in C;
  • the set C is closed under transposition;
  • the linear span of C is an algebra (closed under matrix multiplication).

The axioms, of course, have a combinatorial interpretation, which you can work out with sufficient diligence.

The configuration is homogeneous if the second condition is replaced by the stronger version asserting that the identity is one of the matrices in C. If in addition all the matrices in C are symmetric, we speak of an association scheme. (I am aware that different terminology is used by different authors here; I have discussed this elsewhere, but let me use my own preferred conventions here.)

For much more on this, see several talks at last year’s Pilsen conference, which can be found here.

Now the definition of a (homogeneous) Jordan scheme is obtained from that of an association scheme by replacing matrix multiplication by the Jordan product AB = (AB+BA)/2.

It is easy to see that, if we take a homogeneous association scheme and “symmetrise” it (by replacing a non-symmetric matrix in C and its transpose by their sum) is a homogeneous Jordan scheme.

My question, which Klin, Muzychuk and Reichard have answered negatively, was:

Is every homogeneous Jordan scheme the symmetrisation of a homogeneous coherent configuration?

So now it makes sense to say that a homogeneous Jordan scheme is proper if it is not the symmetrisation of a homogeneous coherent configuration, and to develop the theory of such objects, as Klin, Muzychuk and Reichard have begun to do.

The example

Actually they have many examples, but I will briefly describe the first one, based on a presentation by Sven Reichard at the Slovenian graph theory conference today.

Start with the alternating group A5 acting transitively on 15 points, the stabiliser of a point being the Klein group V4. Because this subgroup is contained with index 3 in A4, the group is imprimitive, with five blocks of size 3. So apart from equality, there are two invariant relations forming five ordered triangles and the reverse, and three further symmetric relations.

One of the triangles is the island, and the other four make up the continent. The edges joining the island to the continent are called bridges, and are of three colours (corresponding to the three further symmetric relations). Now swap two of the colours on the bridges, leaving the remaining edges alone. Symmetrising the resulting structure gives a homogeneous Jordan scheme, which is proper.

Questions

Here are a few questions which could be looked at.

  • Does the Jordan–von Neumann–Wigner theorem have any relevance to proper Jordan schemes? In particular, is there one whose Jordan algebra involves the exceptional simple Jordan algebra?
  • Given a connected simple graph, think of it as an electric circuit, where each edge is a one-ohm resistor. The effective resistance between pairs of terminals defines a metric, called resistance distance, on the vertex set. This is a refinement of the graph structure, similar to that produced by the symmetric version of Weisfeiler–Leman stabilisation. What is the precise relation between these concepts? (Misha Klin, to whom I owe this post, points out that Misha Kagan and Doug Klein have papers relevant to this question.)

Pascual Jordan

Curiously enough, the name of Pascual Jordan (who introduced Jordan algebras) came up in a completely different context yesterday; I would like to say a bit about him.

Jordan is described as one of the unsung heroes of quantum mechanics. It was in a joint paper by Born, Heisenberg and Jordan that the matrix mechanics approach to quantum mechanics was first published (as opposed to Schrödinger’s wave function approach). It is said that the mathematics of matrices in the paper is Jordan’s work. The Nobel Prize was awarded to Heisenberg, Schrödinger and Dirac. Jordan also invented Fermi–Dirac statistics, but because of an unfortunate publication delay he was beaten into print.

According to the MacTutor biography, the reason for the neglect may have been in part his membership of the Nazi party. He wrote in support of the party, but strongly opposed the more extreme views of Ludwig Bieberbach, who believed that there was a real difference between say “French mathematics” and “German mathematics”, and that teaching “German mathematics” to children would increase their “Germanness” (to put it rather crudely).

Anyway, the context in which Jordan’s name came up was a very entertaining lecture given by one of this year’s St Andrews honorary graduands, Jim Al-Khalili, on the new subject of quantum biology. He pointed out that the first paper ever written on quantum biology was by Pascual Jordan, although nobody took it very seriously at the time. It was generally thought that quantum systems would decohere so rapidly in the messy, hot surroundings of a living cell that no effects would be observed. Jim put the opposite “spin” on it: rather than the environment interfering with they system, we can regard the system as exporting information to the environment. It is possible that European robins detect the Earth’s magnetic field (for navigational purposes) by a quantum effect in the bird’s eye, where the collapse of entanglement gives a signal which can be transmitted to the brain by the optic nerve.

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

Position at St Andrews

We have just advertised a lectureship in Pure Mathematics. The advertisement is here.

Come join us!

Posted in Uncategorized | Tagged | Leave a comment

Combinatorics at Strathclyde

Two years ago, we enjoyed a successful British Combinatorial Conference at the University of Strathclyde in Glasgow. For me it was memorable for several reasons: the appearance of my book “Notes on Counting”, my fall to the floor during the ceilidh, the booksale, and (more seriously) some fine lectures including Graham Farr’s lecture commemorating Bill Tutte’s centenary.

Now the Combinatorics group at Strathclyde (David Bevan, Sergey Kitaev and Einar Steingrímsson) is under threat.

I have received two documents; one on reshaping the Department of Computer and Information Sciences, signed by the Head of Department; and a response from the three members of the Combinatorics group.

The first document is pretty much what you might expect, with lots of fine words about “emerging vision”, “imperative”, “resources … aligned with opportunities for future growth”. Mathematics finds no place in this emerging vision.
I quote:

Combinatorics is not considered to be of fundamental importance to UG-teaching. More broadly speaking, discrete mathematics is of fundamental importance but this can be covered by many staff (eg MSP, Data Analytics and Cybersecurity staff) in the Department.

And more along the same lines. In particular, the group is castigated for not getting “grants around a million pounds or more”. [How many mathematicians anywhere hold such grants?]

The response is a much better written and argued document. (Mathematicians, after all, have to be clear – it is an important part of the job – so I am not at all surprised by this.)

They point out that the three-member group is one of the very strongest research groups in the department, having produced 35% of the department’s four-star papers in the current REF and earning REF and grant funding of close to a million pounds in the last four years. Moreover, discrete mathematics underpins computer science, and the group (being the departments only experts in the area) have developed courses for this. Members of the group have had important administrative roles in the department, having greatly improved systems for interacting with PhD students (criticised in an earlier report).

Moreover, combinatorics, or discrete mathematics (the terms are closer in meaning than the Head of Department seems to think, and if there is a difference, the group’s expertise is broader than “just combinatorics”) is perhaps the most applicable part of mathematics in the information age.

Last year, the Bond report, titled “The era of mathematics”, highlighted the importance of knowledge exchange in mathematics, argued (with many examples) that all parts of mathematics can have application, and pushed for a big increase in funding for mathematics, especially the training of PhD students and postdocs. The Council for the Mathematical Sciences has set up two committees to push forward with this, one to prioritise the recommendations in the Bond Report, and the other to convince policymakers of their importance. I would have thought that Strathclyde would be well-placed to benefit from this, if it is successful. (But not of course under the current reshaping plan.)

There have, sad to say, been several instances in Britain of universities closing down mathematics or getting rid of mathematicians in other ways. One incident that sticks in my mind, in a case where I was involved, occurred when the head of another department, at the start of an interview with the committee, said “I couldn’t hold up my head to be in a University with no mathematics department”. In another case, mathematics was closed down so that computer science could expand; this computer science department now finds that its main job consists of teaching arts students how to switch on the computer. (I exaggerate, but not too much.)

It seems to me that the Strathclyde proposal is a very short-sighted move, and unlikely to be in the department’s long-term interest. Moreover, there is plenty of evidence that collaboration between mathematicians (either a department of them, or a group in a computer science department) and informaticians can be of enormous benefit to both.

If you feel as I do, you may wish to know that the head of Computer and Information Sciences at Strathclyde is Professor Neil Ghani. I am sure you can find his address; you can probably even guess it. You may also wish to contact higher authorities in the University. These are our friends and colleagues; please help if you can.

Posted in Uncategorized | Tagged , , , | 20 Comments

Tuna Altınel

Many of you have probably already heard the news that Tuna Altınel, a mathematician of Turkish nationality working in France, was arrested on a family visit to Turkey. His alleged crimes are signing a petition requesting peace talks, and taking part in a public meeting in Lyon “displeasing to the Turkish government”.

You can find latest news here. This website also explains what you can do to help.

Please do anything you can to call for his immediate release.

Posted in Uncategorized | Tagged | Leave a comment