The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a synchronizing word is $O(n^3)$. Let's say that two states are merged by a word if that word takes the two states to the same state. A pumping lemma type argument shows that in a synchronizing automaton, any two states can be merged by a word of length at most $n^2$. Suppose that the following conjecture is true.
Conjecture. Any subset of $k$ states contains two states that can be merged by a word of length (say) at most $n^2/k$. Or more generally, any large set of states contains two that can be merged by a word of length $o(n^2)$.
Then we can consider the following strategy for constructing a synchronizing word. We start with all $n$ states. By the conjecture above, there is a short word merging two states, and we make this the beginning of our synchronizing word. We can run the DFA with this word starting from all states, and we get a set of at most $n-1$ final states. We repeat this with these final states as our new start states. After repeating this a sufficient number of times, we only end up with one final state. Clearly, given the above conjecture, we would have a better bound than $O(n^3)$ for the length of the shortest synchronizing word.
The above motivates the following questions:
- Are there any known counterexamples to this conjecture? Cerny's original construction (see page 18) satisfies the statement of the conjecture.
- Could you provide a reference where similar ideas are investigated?