Trahtman, Avraham

▪ 2009

Avraham Trakhtman 

born Feb. 10, 1944, Kalinovo, Sverdlovsk oblast, U.S.S.R. [now in Russia]

  The astonishing news emerged in 2008 that in September 2007 a 63-year-old Israeli mathematician, Avraham Trahtman, had solved a long-standing problem in graph theory. The road-colouring conjecture, as it was known before being solved by Trahtman, was first suggested in 1970 by the Israeli-American mathematician Benjamin Weiss and the American mathematicians Roy L. Adler and L. Wayne Goodwyn. The theorem concerns a special type of graph, or network, that fulfills certain conditions. The network must have a finite number of vertices (specific locations, or points) and directed edges (one-way paths), be strongly connected (a path must exist from any vertex a to any other vertex b and a path from b to a), and aperiodic (essentially, the cycles, or complete routes following different directions, must be independent). The road-colouring theorem asserts that for such a network, there always exists a synchronized colouring, or method of labeling the edges, to create a map with a simple set of directions, possibly involving many repetitions of the directions, that will lead from any starting point to any other given point. In other words, by following simple directions, such as to take a “red-blue-red” path, it is possible to start from any location and be certain to end up at the desired destination. The existence of such “universal maps” has theoretical implications for real-life problems in computer science, though having a universal map is not the same as having the most efficient route for any individual case.

      Trahtman earned an undergraduate degree (1967) and a graduate degree (1973) in mathematics from Ural State University, in Sverdlovsk (now Yekaterinburg, Russia). He taught in that same city at the Ural State Technical University (1969–84) and at the Sverdlovsk Pedagogical University (1991–92) before immigrating to Israel in 1992. Like many of the recent immigrants following the breakup of the Soviet Union, Trahtman had difficulty finding an academic position, and he first accepted work as a security guard and lectured (1994–95) part-time in the pre-education department at Hebrew University in Jerusalem. In 1995 Trahtman obtained a professorship at Bar-Ilan University in Ramat Gan, near Tel Aviv.

      Trahtman's solution is notable for its brevity: at less than eight pages it is extremely concise and considered quite elegant. The proof is also rather noteworthy in that most major mathematical breakthroughs come from individuals before the age of 40, or even 30. Trahtman proved, however, that age was not a barrier to solving a nearly 40-year-old mathematical conundrum.

William Hosch

* * *