Short Synchronizing Words for Random Automata

We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ω of such length, and a state v0, such that ω sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykuła [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ω we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p.. Our proof introduces the concept of ω-trees, for a word ω, that is, automata in which the ω-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ω-tree for some word ω of length at most (1 + ε) log2(n), for any ε > 0. The existence of the (random) word ω is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.