## 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

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:

- Introduction
- Permutation groups
- Synchronizing and separating groups
- Graph homomorphisms
- Graphs and monoids
- Examples
- Representation theory
- The infinite
- Exercises, open problems, references

Hard copy should be available to course participants.
Peter J. Cameron

3 June 2010