Trahtman, Avraham

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

* * *


Universalium. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Avraham Trahtman — Infobox Scientist name = Avraham Trahtman box width = | image width = caption = birth date = birth place = death date = death place = residence = Jerusalem, Israel citizenship = nationality = ethnicity = field = Mathematics work institutions =… …   Wikipedia

  • Synchronizing word — This drawing represents a DFA with eight states and two input symbols, red and blue. The word blue red red blue red red blue red red is a synchronizing word that sends all states to the yellow state; the word blue blue red blue blue red blue blue …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • List of mathematicians (T) — NOTOC Tac * Tachard, Guy (France, 1651 1712) * Tacquet, André (Belgium, 1612 1660) * Taguchi, Genichi (Japan, 1924 ) * Tahan, Malba (Brazil, 1895 1974) * Tahta, Dikran (Britain, 1928 2006) * Taimina, Daina (Latvia, ? ) * Tait, Peter Guthrie… …   Wikipedia

  • Синхронизируемое слово — «»В компьютерной науке, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние[1]. То есть, если… …   Википедия

  • Трахтман, Абрам Наумович — В Википедии есть статьи о других людях с такой фамилией, см. Трахтман. Абрам Наумович Трахтман Дата рождения …   Википедия

  • Road coloring problem — In graph theory the road coloring theorem, known until recently 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… …   Wikipedia

  • Unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Millennium Prize Problems Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, the six ones yet to be solved are:… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”