Synchronizing Times for $k$-sets in Automata
An automaton consists of a finite set of states and a collection of functions from the set of states to itself. An automaton is synchronizing if there is a word (that is, a sequence of functions) that maps all states onto the same state. Cerny's conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps $k$ states onto a single state. For synchronizing automata, we have improved the upper bound on the minimum length of a word that sends some triple to a a single state from $0.5n^2$ to $\approx 0.19n^2$. I will discuss this result and some related results, including a generalisation of this approach this to an improved bound on the length of a synchronizing word for $4$ states and $5$ states. This is joint work with Robert Johnson.