Intensive course on Synchronization

Lecturer: Peter J. Cameron (QMUL)

10–11 June 2010, De Morgan House

A (finite-state deterministic) automaton is synchronizing if there is a sequence of transitions which brings the automaton to a fixed state from an arbitrary starting point; in other words, the monoid generated by the transitions of the automaton contains a constant function. Such a sequence is called a reset word.

The celebrated Černý conjecture asserts that if an n-state automaton has a reset word, then it has one of length at most (n–1)².

An approach to this conjecture (not so far successful!), suggested by Ben Steinberg and João Araújo, brings together automata theory, permutation groups, representation theory, graph homomorphisms, extremal combinatorics, and finite geometry.

The course will introduce the various topics mentioned above and explain some of their connections.

Course details and registration

• LTCC Intensives page
• Course description

Note to students and others intending to attend the course:

I intend to make the course self-contained as far as possible. However, the material on permutation groups and on finite geometries is somewhat technical. You may wish to do some preliminary reading before the course. I recommend the following:

• Peter J. Cameron, Permutation Groups, London Math. Soc. Student Texts 45, Cambridge University Press, Cambridge, 1999, Chapters 1, 2, 4.
• Peter J. Cameron, Projective and Polar Spaces, QMW Maths Notes 13 (1991), Chapter 6, available from http://www.maths.qmul.ac.uk/~pjc/pps/.

Course materials

Lecture notes for the course:

1. Introduction
2. Permutation groups
3. Synchronizing and separating groups
4. Graph homomorphisms
5. Graphs and monoids
6. Examples
7. Representation theory
8. The infinite
9. Exercises, open problems, references

Peter J. Cameron
3 June 2010