# A conjecture related to the Cerny conjecture - counterexample/reference request

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:

1. Are there any known counterexamples to this conjecture? Cerny's original construction (see page 18) satisfies the statement of the conjecture.
2. Could you provide a reference where similar ideas are investigated?