Avraham Naumovich Trahtman (Trakhtman) (russian: Абрам Наумович Трахтман; b. 1944,

USSR The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen nationa ...

) is a mathematician at Bar-Ilan University (

Israel Israel (; he, יִשְׂרָאֵל, ; ar, إِسْرَائِيل, ), officially the State of Israel ( he, מְדִינַת יִשְׂרָאֵל, label=none, translit=Medīnat Yīsrāʾēl; ), is a country in Western Asia. It is situated ...

). In 2007, Trahtman solved a problem in

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

that had been open for 37 years, the

Road Coloring Conjecture In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with Synchronization, synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destinati ...

posed in 1970.

Road coloring problem posed and solved

Trahtman's solution to the

road coloring problem In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any othe ...

was accepted in 2007 and published in 2009 by the ''

Israel Journal of Mathematics '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the jou ...

''. The problem arose in the subfield of symbolic dynamics, an abstract part of the field of

dynamical systems In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a p ...

. 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.

Černý conjecture

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 computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state.Avraham Trakhtma ...

. In 1964 Jan Černý conjectured that

(n-1)^2

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). (in Slovak). English translation
A Note on Homogeneous Experiments with Finite Automata
J. Autom. Lang. Comb. 24(2019), 123-132 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

n (7n^2+6n-16)/48

, but then he found an error in it. The conjecture holds in many partial cases, see for instance, Kari and Trahtman.

Other work

The finite basis problem for semigroups of order less than six in the theory of semigroups was posed by Alfred Tarski in 1966, and repeated by

Anatoly Maltsev Anatoly Ivanovich Maltsev (also: Malcev, Mal'cev; Russian: Анато́лий Ива́нович Ма́льцев; 27 November N.S./14 November O.S. 1909, Moscow Governorate – 7 June 1967, Novosibirsk) was born in Misheronsky, near Moscow, and ...

and L. N. Shevrin. In 1983, Trahtman solved this problem by proving that all semigroups of order less than six are finitely based. In the theory of varieties of semigroups and

universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study, ...

s the problem of existence of covering elements in the lattice of varieties was posed by Evans in 1971. The positive solution of the problem was found by Trahtman. He also found a six-element semigroup that generates a variety with a continuum of subvarieties, and varieties of semigroups having no irreducible base of identities. The theory of locally testable automata can be based on the theory of varieties of locally testable semigroups. Trahtman found the precise estimation on the order of local testability of finite automata. There are results in theoretical mechanics and in the promising area of extracting moisture from the air mentioned in "''

New Scientist ''New Scientist'' is a magazine covering all aspects of science and technology. Based in London, it publishes weekly English-language editions in the United Kingdom, the United States and Australia. An editorially separate organisation publishe ...

''".F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.

References

External links

Trahtman's page at Bar-Ilan University's WebsiteTrahtman's paper (in PDF format)"63-year-old solves riddle from 1970" on MSNBC"Encyclopedia - Britannica Online Encyclopedia", article: Avraham Trahtman"MacTutor History of Mathematics. Trahtman biography"''A Mathematical Medley Fifty Easy Pieces on Mathematics''
by George G. Szpiro {{DEFAULTSORT:Trahtman, Avraham Academic staff of Bar-Ilan University 1944 births Living people Israeli Jews 21st-century Israeli mathematicians Russian Jews 20th-century Israeli mathematicians Ural State University alumni