You couldn’t make it up

A warning came round on the departmental email list that “NERC recently started to office reject grant applications containing incorrect font sizes”. It seems that their regulations state:

Principal Investigators should ensure that all proposal contributors are aware of and meet the submission regulations set out in the NERC handbook e.g. attachments should be of the correct length, font size etc. Please see paragraph 171. of the NERC grants handbook for detailed regulations. Proposals not adhering to the rules will be automatically rejected and will not be returned to applicants for corrections.

Posted in Uncategorized | Tagged , | 12 Comments

Journal of Computation and Mathematics

The London Mathematical Society includes in its portfolio a single diamond open access journal, the Journal of Computation and Mathematics.

But not for much longer, if the LMS Council has its way.

A group of interested persons (whose names have not been revealed in correspondence from the LMS to its members) have called for a Special General Meeting of the society to discuss the issue, so it is possible that the decision may be changed.

Please make up your own mind about this and act accordingly. But I would make two points, hopefully uncontroversial.

  1. The LMS claims that in the 18 years of its existence the journal has cost £380,000 to run. (No breakdown of this figure is given.) Given that Tim Gowers has found an organisation to run his new arXiv overlay journal Discrete Analysis at $10 per submission, it seems that either the journal has been inundated with submissions, or the LMS has not run it very efficiently.
  2. At a time when academic publishing is in a state of flux, it seems a bit rash to close down one publishing model which might have an important contribution to make.
Posted in publishing, the LMS | Tagged , | 2 Comments

The synchronizing monster

Pirates of Pangaea

Today, a long paper on synchronizing groups (108 pages), by João Araújo, Ben Steinberg, and me, appears on the arXiv.

It has been a long time coming. To quote from a post of mine in 2010,

I became involved in this subject because of a syzygy of three independent events in January 2008. First, I had been working with Cristy Kazanidis on cores of rank 3 graphs; we had come to the conjecture that for such a graph, either the core is complete, or the whole graph is a core. At about the same time, somebody asked me about a talk at the Oberwolfach meeting on permutation groups the previous summer; so I got out the report of the meeting, and happened to notice Peter Neumann’s talk on a strengthening of the notion of primitivity [which had been proposed by João Araújo]. And then Robert Bailey, at the time a postdoc in Ottawa, showed up, and (among other things) told me about a conversation he had had with Ben Steinberg at the bus stop, which had been interrupted when Ben’s bus arrived.

I discovered that all these things were closely connected.

This paper is the story of at least some of the connections.

Everybody I talked to about synchronization became very enthusiastic about this beautiful subject. We formed ourselves into a “Synch Co-op”, and started proving theorems and writing programs. Then, for some reason (for which the blame probably falls on me), the project lost momentum. We continued proving theorems and writing programs, but the definitive account never got written. So that when the last International Review of UK mathematics took place in late 2010, and they wanted to commend the work on synchronization, they had to refer to the notes of my LTCC intensive course on the subject.

Well, it is written now. Read it and enjoy, and solve some of the problems! Whether you are a finite geometer, extremal combinatorialist, representation theorist, group theorist, semigroup theorist, automata theorist, …, there is something in it for you! The paper ends with a list of 40 open problems.

In brief,

  • Automata theory: we have something new on the celebrated Černý conjecture, a famous and nearly 50-year-old problem. [Not a proof of the conjecture, sad to say!]
  • Semigroup theory: This is the context. When does the transformation semigroup generated by a permutation group and one non-permutation group contain a constant function?
  • Group theory: We have a hierarchy of classes of permutation groups lying between the primitive and the 2-homogeneous groups. In almost all cases, these classes are known to be distinct.
  • Finite geometry, combinatorics: testing the synchronizing property for specific classes of permutation groups includes many hard problems including the existence of ovoids and spreads in polar spaces, the existence of Steiner systems (and large sets), the Hadamard conjecture, Baranyai, Erdős–Ko–Rado, …
  • Representation theory: read the paper for some interesting methods, results and conjectures!
  • Graph endomorphisms: all of the lower levels of the hierarchy can be translated into questions about graph endomorphisms. Indeed, a necessary and sufficient condition for a transformation monoid not to contain a function is that it is contained in the endomorphism monoid of a graph, and the graph may be assumed to have clique number and chromatic number equal. I still find this quite remarkable.
  • Computational complexity: there may be interesting things here; we are trying to solve problems which are hard in general, but we know quite a lot about the graphs we are solving them on as a result of the Classification of Finite Simple Groups.
  • Tales of adventure: solving these problems will help the princess to escape from the pirates!

Two of the authors managed to sneak into the photo of Laci Babai in my last post. I am afraid I don’t have a good photo of Ben, but you can see him here. (I am the real interloper, since it was the other two who first defined synchronizing groups, as my story suggests.)

PS The picture is from Pirates of Pangaea, by Daniel Hartwell and Neill Cameron.

Posted in exposition, history, Neill Cameron artwork | Tagged , , , , , , , , , , | 2 Comments

Graph isomorphism

I just read Ken Regan’s report on the Gödel’s Last Letter blog that Laci Babai has a quasi-polynomial algorithm for graph isomorphism

“Quasi-polynomial” means exp(O((log n)c)) for some c: c = 1 would be polynomial.

Congratulations Laci!

Oh, and here he is at my retirement bash:

Araujo, Babai, Cameron

Posted in Uncategorized | Tagged , | 2 Comments

Waterbirds of Portugal


The flamingoes and egret are on the lagoon in Aveiro. Despite appearances, the boat in the bottom picture is not one of the famous moliceiros or seaweed-gathering boats of Aveiro, but was at Alcochete, a fishing village on the south bank of the Tejo; a group of foraging spoonbills is passing it. These boats are traditional here, and I believe they are connected with the Aveiro boats.

Actually, if I want to see egrets, I can just look out the back of the apartment: there are usually between five and thirty on the grassy slope there.

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



Many houses in Prague have a symbol of some kind on the door, often an animal. This house near the Malastrana end of the Charles Bridge has a star. The original has the star painted in the same colour as the wall, but I recoloured it using coloured pencils (more correctly, colours sampled from the web page of a famous brand of coloured pencils). As appropriate for pencils, I sharpened the points a bit.

The waterlily is in a pond on the campus of the University of Exeter.

Posted in Uncategorized | Tagged , | 1 Comment

The 42 professors

The street atlas of Lisbon in the apartment lists 50 streets named after professors, from Rua Professor Abel Salazar to Rua Professor Vitor Fontes.

Because some of the names are duplicated, there are only 42 or 43 professors who are actually commemorated in this way. (I put 42 in the title because I guess that Professor Fernando Fonseca is probably the same person as Professor Fernando de Fonseca.)

Nonetheless, it seems like a very large number. Can you think of any other city which commemorates so many professors in this way?

You might expect them to cluster round the University, but in fact the Universidade de Lisboa has just two streets in this category, Av. Professor Gama Pinto and Av. Professor Anibal de Bettencourt.

This suggests a society in which a professor is respected, and more generally in which learning is valued. I hear hollow laughter from my Portuguese colleagues, but I think this must at least have been so once in order for this riot of naming streets after professors to have occurred.

Posted in Uncategorized | Tagged | 2 Comments