Born: 10 February 1944 in Kalinovo, Sverdlovsk oblast, USSR (now Russia)

Abram Naumovich Trakhtman (or Trahtman) is usually known as Avraham Trahtman. His father was Naum Trakhtman, who was born in the town of Sokiryani (or Sokyryany) in the Bukovina region of south-west of Ukraine. Naum was a watchmaker who did not finish his schooling in Romania. Naum Trakhtman's father, Idel Trahtman, was living in Sokiryani during the tragic events of World War II. After the German armies invaded this region, it was given to Romania since they were allies of Germany, then later it was retaken by the Russians. The Trahtman family were Jewish and so suffered greatly during this period. Idel was killed in the Jewish genocide that took place during this period and several of his young grandchildren died from hunger and deprivation. Naum Trakhtman served in the Red Army during World War II but in 1950 he was arrested and beaten to death during interrogations. His arrest was in connection with the many clocks and watches which flooded into the Soviet Union after World War II, something which greatly angered the authorities. Avraham's mother came from the city of Gomel (now Homel in Belarus) and she belonged to the family Vilyatsery whose traditional profession was as turners of wood and metal. The Jewish Vilyatsery family had a tradition to alternate the names Abraham and Aaron.

As a young boy, Avraham liked playing draughts (checkers). He was also good at sports and took part in sporting competitions. He attended the school N 19 in Gomel from 1951 to 1962. After graduating from this school, he entered the Ural State University in Sverdlovsk (now Ekaterinburg or Yekaterinburg) in 1962. He studied mathematics at university and completed his undergraduate studies in 1967 and was awarded his degree. Following this, he was appointed as an assistant in the Department of Computational Mathematics in the Ural Technical University in 1969 and continued to teach there until 1984 rising to the rank of associate professor. His teaching included courses on linear algebra, applied mathematics, general algebra, statistics, and discrete mathematics. During the years 1970-72 he undertook research in mathematics in Lev Shevrin's research group at the Ural State University working on semigroup theory. Lev Shevrin was Trahtman's thesis advisor and, despite some deliberate obstacles put in his way due to his being Jewish, Trahtman was awarded his Ph.D. in 1973.

In the years before the award of his Ph.D., Trahtman published a number of papers with V A Baranskii (written in Russian) such as: Half-isomorphisms of matrix bands of semigroups with cancellation law (1968); Lattice isomorphisms of matrix bands of nonperiodic commutative semigroups with cancellation law(1969); and Subsemigroup graphs (1970). In 1971 he published the paper Die einstufig nichtkommutativen Halbgruppen mit Ausnahme von unendlichen Gruppen written jointly with László Rédei. This paper was not written because the two mathematicians had worked together on a problem, rather it came about as the consequence of both independently having proved the same results at about the same time and deciding that the fairest course of action was to publish a joint paper. Trahtman published Covering elements in the lattice of varieties of algebras (Russian) in 1974 which contained material from his Ph.D, dissertation. The paper proved a conjecture made by Evan two years earlier. He then looked at the 'Tarski problem'.

The Tarski problem, which Alfred Tarski posed in 1966, asked whether semigroups of small order had a finite base for their identities. Anatoly Ivanovich Malcev and Lev Shevrin also looked at this problem to which Trahtman made a major contribution in proving that all semigroups of order less than six have a finite base for their identities. However, publishing this result proved surprisingly difficult, not for mathematical reasons, but rather for political ones. Trahtman had been investigated by the KGB as a possible spy and this led to difficulties being made when he tried to publish his work. His strong support of the Jewish cause meant that his life as an academic was severely hampered. However, during the late 1980s under Gorbachev's leadership, the policy of 'glasnost' was introduced leading to a much greater freedom of expression and open criticism of the political order became possible throughout the USSR. Trahtman was a strong advocate of democracy and became an influential figure in the Sverdlovsk political associations 'Rally-87' and 'Democratic Choice', and in the national movements 'Democratic Russia' and the SDPR.

In 1991, Trahtman was appointed as an assistant professor in the Department of Mathematics of Sverdlovsk Pedagogical University. He also taught courses in algebra and its applications, and finite mathematics at the Sverdlovsk State Pedagogical Institute. In 1992 he was able to leave the USSR and emigrate to Israel following the breakup of the former Soviet Union. However, he had no academic position in Israel and, being one of a huge wave of immigrants leaving the former Soviet Union, he struggled to find any work at all. He had various jobs in Israel including maintenance work and a stint as a security guard before being appointed as a part-time lecturer in the Pre-education Department of the Hebrew University, Jerusalem, in 1994. In the following year he was appointed at Bar-Ilan University, in Ramat Gan near Tel Aviv, largely due to the efforts of Stuart Margolis, a professor at the Department of Mathematics at Bar-Ilan University. Margolis commented [6]:-

When he applied for work at Bar-Ilan, a colleague of mine noticed that Avraham was in the same field as mine. I had heard of him before, as he had written very important papers. When he applied for a job in the mathematics department, he was hired to teach and do research.

Margolis also remarked [2]:-

The first time I met him he was wearing a night watchman's uniform.

And is quoted in [4]:-

... here is a guy who had a good reputation for his work in the Soviet Union and couldn't get work.

At Bar-Ilan University, Trahtman taught courses in discrete mathematics, theory of sets, algebra, analytical geometry, mathematical logic, finite automata, formal languages, rings and modules, and differential equations. His research interests have, however, have continued to be related to the topics on which he first began working. He explains:-

My first publications were [in semigroup theory], in particular, the solution of the Tarski problem ..., the properties of finite semigroup generates class of locally testable semigroups and automata. Locally testable automata with generalizations and synchronizing automata are still the main topics for me. The package TESTAS realizes some my algorithms in this area.

He created the computer:-

... package TESTAS for verification of local testability and its generalizations (threshold, right, left, bilateral, piecewise and other) for both transition graphs of automata and transition semigroups, for checking synchronizability and finding synchronizing words, for finding transition semigroup of automaton.

His greatest achievement, however, has been in solving the 'Road Colouring Problem'. The problem basically concerns an undirected graph and asks if its edges can be labelled by colours so it is possible to give a list of colours so that, no matter which vertex one starts from, then following the path indicated by the colours one will always arrive at the same specified vertex. The problem was first proposed by Benjamin Weiss, Roy L Adler and L Wayne Goodwyn. A more technical description of what Trahtman achieved is given by him in the abstract for seminars he has given on the Road Colouring Problem. For example, the abstract of a seminar he gave on 4 November 2007 reads:-

A synchronizing word of a deterministic automaton is a word in the alphabet of colours (considered as letters) on its edges that maps the automaton to a single state. A colouring of edges of a directed graph is synchronizing if the colouring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road colouring problem originated in 1970 and was stated explicitly in 1977 by Adler, Goodwyn and Weiss for a strongly connected directed finite graph with constant outdegree of all its vertices where the greatest common divisor of lengths of all its cycles is one. The edges of the graph are unlabelled. The road colouring problem is connected with the problem of existence of synchronizing word for deterministic complete finite automaton. The problem is important in automata theory: a synchronizing colouring makes the behaviour of an automaton resistant against input errors since, after detection of an error, a synchronizing word can reset the automaton back to its original state, as if no error had occurred. The problem appeared first in the context of symbolic dynamics. It evoked noticeable interest among the specialists in the theory of graphs, automata and symbolic dynamics and is discussed even in "Wikipedia", the popular Internet Encyclopedia. Together with the Cerny conjecture, the road colouring problem belongs to the most fascinating mathematical problems in the theory of finite automata. We present a solution of the road colouring problem.

Marcus du Sautoy give this less technical version in [4]:-

You have a map marked with lots of cities (represented by dots) and a set of roads running between these cities (the roads are then lines joining the dots). The roads are all one-way roads so you can only go along them in one direction. Suppose you live in one of the cities on this map. I'm in another city. You want to give me instructions which will get me from my city to your city. But you don't know where I am. Is there a way to colour the roads and a set of instructions like (take a red road followed by a blue road followed by another blue road followed by a yellow road) so that where ever I am in the map, the set of instructions will always get me to your city. Quite amazingly you can do this, though there are some technical conditions that limit the kind of network for which this works. It isn't possible on every network. These network problems are really fun to play about with. Quite often it just requires a cunning new way to think about the problem and a solution drops out. Unlike Fermat's Last Theorem which required lots of technical and sophisticated mathematical techniques to crack, the maths behind Trakhtman's solution is not complicated, it just required a clever new way to look for the solution. In a way it's a bit like trying to come up with a universal set of rules that will solve a sudoku puzzle regardless of how the numbers are put into the boxes.

Stuart Margolis said [6]:-

Articles:

1. M du Sautoy, Sexy maths: ditch the GPS, just follow the colour code, The Times (4 March 2009).
2. Israeli ex-security guard solves 38-year-old math problem, Haaretz Newspaper (20 March 2008).
   http://haaretz.com/hasen/spages/966679.html
3. A Heller, Security guard solves 38-year-old maths poser, The Guardian (Friday 21 March 2008).
4. R Highfield, Directions from anywhere: maths problem solved, The Telegraph (21 March 2008).
5. K Kloosterman, Israeli immigrant solves 38-year-old math problem, ISRAEL21c (18 February 2008).
6. J Siegel-Itzkovich, Russian immigrant solves math puzzle, The Jerusalem Post (8 February, 2008).