Synchronization

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.

The Dungeon

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.

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition, open problems, synchronization, teaching. Bookmark the permalink.

8 Responses to Synchronization

  1. Olof Sisask says:

    Your example with the caves reminds me of the following puzzle. You find yourself in front of a castle with two doors, and in front of each door there is a guard. You know that one of the doors leads to instant greatness and the other to instant doom; you also know that one of the guards always tells the truth and the other guard always lies. The guards know which door leads where, and you are allowed to ask one guard one question in order to find the door that leads to greatness. How can you do it?

    I also just remembered the following idle thought that once popped into my head; it is perhaps more directly related to your example. Suppose you have a calculator that has an ‘On’ button but no ‘Off’ button — instead you press ‘Shift’ and then ‘On’ to switch the calculator off. The ‘Shift’ key only works when the calculator is on. If you can’t see the display, what is the minimum number of keystrokes needed to make sure the calculator is off regardless of its initial state?

    The answer is fairly obvious in this setup, however…

  2. The calculator example is nice. There is a reset word of length 1, namely “On”, which always leaves the calculator on; then “Shift-On” will turn it off. In this case the Černý bound is (2-1)^2=1 which is attained; and in fact this example is the first in an infinite sequence of examples attaining the bound.

    As to the guards, there is a variant in which the guards speak a language which you also know somewhat; you know the words for “yes” and “no” but don’t recall which is which…

  3. I have created a web page for the course, which you may want to look at if you are thinking of attending. The address is

    http://www.maths.qmul.ac.uk/~pjc/LTCC-2010-intensive3/

    I expect to put preliminary versions of some of the course material there shortly.

  4. Dima says:

    There seems to be a mild discrepancy: after Thm 12 in Lect.3 there is a remark basically saying that it is not known whether a spreading group must be 2-homogeneous, and Thm 6 in Lect.7 essentially gives examples (certain affine groups) that *are* spreading without being 2-homogeneous.

  5. You are right – thanks! It will be fixed… The big mystery is whether spreading is the same as QI.

  6. Dima says:

    Another typo, in Lect. 6 after Example 10 the groups are P\Omega(5,q), not P\Omega(4,q).

  7. Thanks Dima, you are doing a great proofreading job!

    It is curious (i.e. I don’t know the reason why) these three groups, in their other action (as PSp(4,q), which Pablo showed with some difficulty to be non-spreading…

  8. Pingback: Synchronization, and sad news « Peter Cameron's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s