Avraham Trakhtman

Avraham Naumovich Trakhtman (also Trahtman), (born February 10, 1944 in Kalinowo , Sverdlovsk Oblast ) is a Soviet-Israeli mathematician.

Trahtman 2008

Trahtman studied at the State University of the Urals in Sverdlovsk with the degree in 1967. He was then at the Technical University of the Urals, where he was a lecturer and taught until 1984. In 1973 he received his doctorate under Lev Shevrin at the Urals State University. Because he was Jewish, his career in the Soviet Union was hampered in the 1970s. At the end of the 1980s he was also active in the Russian democracy movement. In 1991 he became an assistant professor at the Sverdlovsk University of Education, but left the Soviet Union in 1992 and went to Israel. First he had to make do with casual work there before he got a position at Bar-Ilan University in 1995 .

In 1974 he solved a problem by T. Evans (1971) about associations of semigroup varieties.

In 1983 he solved the problem of the finite basis for semigroups by Alfred Tarski (1966).

In 2007, he dissolved the road coloring problem ( Road Coloring Problem ) by Roy Adler , LW Goodwyn and Benjamin Weiss (1970). The problem asks about the existence of a synchronized coloring of the edges in certain directed graphs (the same number of edges lead out of each node, which are all colored differently). The coloring makes it possible to indicate a timetable (as a sequence of colors in a word W) to get from any node P of the graph to another node Q of the graph, where W is the same for all P. The problem has its origin in automata theory.

He also made advances in another open problem in finite automata theory, the Cerny problem (1964, Jan Cerny), an upper bound on the length of the shortest synchronizing words.

Web links

• John J. O'Connor, Edmund F. Robertson :  Avraham Trakhtman. In: MacTutor History of Mathematics archive .
• Homepage

Individual evidence

1. ↑ Trahtman The road coloring problem , Israel J. Math., Volume 172, 2009, pp. 51-60.