Avraham Trakhtman
| Avraham Naumovich Trahtman | |
|---|---|
 |
|
| Born | 10 February 1944 Kalinovo, Nevyansky District, Sverdlovsk Oblast |
| Residence | Jerusalem, Israel |
| Fields | Mathematics |
| Institutions | Bar-Ilan University |
| Alma mater | Ural State University |
| Doctoral advisor | Lev N. Shevrin |
| Known for | solving the road coloring problem |
Avraham Naumovich Trahtman (Trakhtman) (Russian: Абрам Наумович Трахтман; b. 1944, USSR) is a mathematician at Bar-Ilan University (Israel). In 2007, Trahtman solved a problem in combinatorics that had been open for 37 years, the Road Coloring Conjecture posed in 1970.
Trahtman's solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of Mathematics. The problem arose in the subfield of symbolic dynamics, an abstract part of the field of dynamical systems. The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States, and the Israeli mathematician B. Weiss. The proof used results from earlier work.
The problem of estimating the length of synchronizing word has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1964 Jan Černý conjectured that is the upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph). If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number n of states) for which the shortest reset words have this length. In 2011 Trahtman published a proof of upper bound , but then he found an error in it. The conjecture holds in many partial cases, see for instance, Kari and Trahtman.
...
Wikipedia