The synchronizing monster

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.