One of my many jobs over the next month or two is to write a course of lectures on a new subject, Synchronization.
I will be giving an intensive course at the London Taught Course Centre on 10-11 June, eight hours of lectures in a 24-hour period. It has to be all prepared in advance, and ready to roll, by the start of the course; there will be no time f or second thoughts once it is underway.
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 previoius 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. 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.
Ben Steinberg and João Araújo had been thinking about the Černý conjecture in automata theory. A (finite deterministic) automaton is a black box with a number of coloured buttons on the front. It can be in any one of a finite number of internal states; each button, when pressed, causes a specified transition between states. Combinatorially, this can be represented as a directed graph whose vertices are the states; each transition is represented by a directed edge from the initial to the final state, coloured with the colour of the corresponding button; thus, there is exactly one edge of each colour leaving each vertex. Algebraically, each button corresponds to a map from the set of states to itself; we can push a sequence of buttons to induce the composite of the corresponding maps, so an automaton is a transformation monoid on a finite set with a prescribed set of generators.
Imagine that you are in a dungeon consisting of a number of interconnected caves, all of which appear identical. Each cave has a number of one-way doors of different colours through which you may leave; these lead to passages to other caves. There is one more door in each cave; in one cave this leads to freedom, in all the others to instant death. You have a map of the dungeon, but you don’t know in which cave you are. If you are lucky, there is a sequence of doors through whch you may pass which take you to the escape cave from any starting point. The example below shows this.
In the example, the sequence (BLUE, RED, BLUE, BLUE) always brings you to cave number 3 in the bottom right.
Thus, an automaton is synchronizing if there is a sequence of transitions which brings it to the same state no matter where it started; in other words, an element of the monoid generated by the transitions which is a constant function. Such a sequence is called a reset word.
The Černý conjecture asserts that, if an n-state automaton has a reset word, then it has one of length at most (n-1)2. This conjecture was made in 1968 and is still open.
The idea of Araújo and Steinberg was that, since permutations are the “worst” elements for synchronization, we should consider the permutation group G generated by those transitions which are permutations (this contains all the permutations in the monoid), and examine what happens when we add a single non-permutation to G. With slight abuse of language, they call a permutation group G synchronizing if, for any non-permutation f, the monoid generated by G and f contains a constant function. The hope is that one could use the techniques of group theory to bound the length of the corresponding reset word.
In fact, despite some progress, the Černý conjecture has not yet been proved this way; but the subject has made important connections with permutation group theory and (surprisingly) with the theory of graph homomorphisms. A synchronizing permutation group is primitive, but the converse is false, so we have a cass of groups strictly between the primitive and the doubly transitive groups. Also, a permutation group fails to be synchronizing if and only if it is contained in the automorphism group of a non-trivial graph (i.e. not the complete or null graph) whose core is complete. This led easily to a proof of the conjecture on rank 3 graphs that Cristy and I made.
So I have ahead of me the pleasant job of explaining all this.
All are welcome to attend these lectures. You can find an application form on the LTCC web page here.