Synchronizing times for \(k\)-sets in automata (Q2170794)

Summary: An automaton is synchronizing if there is a word that maps all states onto the same state. Černý'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 find a simple argument for general \(k\) almost having the upper bound on the minimum length of a word sending \(k\) states to a single state. We further improve the upper bound on the minimum length of a word sending 4 states to a singleton from \(0.5n^2\) to \(\approx 0.459n^2\), and the minimum length sending 5 states to a singleton from \(n^2\) to \(\approx 0.798n^2\). In contrast to previous works on triples, our methods are combinatorial. Indeed, we exhibit a fundamental obstacle which suggests that the previously used linear algebraic approach cannot extend to sets of more than 3 states. In the case of non-synchronizing automata, we give an example to show that the minimum length of a word that sends some \(k\) states to a single state can be as large as \(\Theta\left(n^{k-1}\right)\).