Open problem, Combinatorics and discrete mathematics, Applied and computational mathematics, posed 1964

Černý conjecture (synchronizing automata)

Open

Every synchronizing deterministic finite automaton (DFA) with $n$ states admits a reset word (synchronizing word) $w \in \Sigma^*$ of length at most $(n - 1)^2$ that sends all $n$ states to a single common state: $|Q \cdot w| = 1$ .

Research frontier as of 2026

As of 2026, the Černý conjecture remains open, and even proving a quadratic upper bound $O(n^2)$ for general synchronizing automata is unsolved. The best known universal upper bound is $\alpha n^3 + o(n^3)$ with $\alpha \le 0.1654$ (Shitov, 2019, refining Szykuła, 2018), while the worst known lower bound remains $(n - 1)^2$ , achieved by Černý's 1964 family $\mathcal{C}_n$ and only finitely many known sporadic extremal automata (all on $n \le 6$ states). The conjecture has been verified for Eulerian, aperiodic, circular, one-cluster, and oriented monotonic automata, and holds with high probability for random synchronizing automata.

Best known results

Every $n$ -state synchronizing DFA has a reset word of length at most $\alpha n^3 + O(n^2)$ with $\alpha \approx 0.1654$ (Szykuła 2018; Shitov 2019), improving the classic Pin–Frankl bound $\frac{n^3 - n}{6}$ .
The Černý bound $(n - 1)^2$ is proved for Eulerian automata (Kari, 1998), circular automata (Dubuc, 1998), aperiodic automata (Trahtman, 2007), and one-cluster automata with prime-length cycle (Steinberg, 2011).

Tools and where they stop

Tool	Achieved	Where it stops
Frankl's skew-cross-intersecting set theorem and avoiding words	Bounds the shortest word compressing a state subset $S$ of size $k \ge 2$ to size $k - 1$ by $\binom{n - k + 2}{2}$ (Pin–Frankl) and refines it via linear-algebraic rank bounds on avoiding words (Szykuła, Shitov).	Summing $O((n - k)^2)$ compression steps over $k = n, n-1, \dots, 2$ inherently produces an $O(n^3)$ bound unless one proves amortised $O(n)$ compression per step.
Linear-algebraic representation of transition monoids (Kari, Steinberg)	Associates matrices to input letters and uses dimension arguments in $\mathbb{R}^n$ combined with stationary distributions of the underlying digraph to establish $O(n^2)$ bounds for Eulerian and one-cluster automata.	General synchronizing automata lack a positive stationary vector or uniform in-degree property, so preimage weights need not increase monotonically along short words.

Open questions

Does there exist a universal constant $C > 0$ such that every $n$ -state synchronizing DFA admits a reset word of quadratic length at most $C n^2$ ?
For $n \ge 7$ , is Černý's automaton $\mathcal{C}_n$ the unique minimal $n$ -state synchronizing automaton (up to isomorphism and redundant letters) achieving reset threshold $(n - 1)^2$ ?

References

Mikhail V. Volkov (2008). Synchronizing automata and the Černý conjecture · DOI:10.1007/978-3-540-78926-0_2
Marek Szykuła (2018). Improving the upper bound on the length of the shortest reset word · DOI:10.4230/LIPIcs.STACS.2018.56 · arXiv:1702.05455
Yaroslav Shitov (2019). An improvement to a recent upper bound for synchronizing words of finite automata · DOI:10.1016/j.jcta.2019.04.007 · arXiv:1901.06542