Avraham Trahtman

Trahtman obtient une maîtrise de mathématiques en 1967 et soutient une thèse en 1973 (titre de la thèse : On The System Of Proper Subsemigroups Of A Semigroup) sous la direction de Lev Shevrin[1] à l'université d'État de l'Oural de Sverdlovsk (maintenant Iekaterinbourg). Il enseigne dans cette ville à l'université technique d'État de l'Oural (en) (1969-1974) et comme professeur assistant à l'université pédagogique de Sverdlovsk (1991-1992).

Trahtman émigre en Israël en 1992, à une époque où nombre de scientifiques russes avaient déjà émigré, provoquant une sorte d'excès de l'offre sur la demande. Ne trouvant pas de travail correspondant à sa formation, Trahtman travaille comme agent d'entretien et gardien de nuit, avant de trouver un emploi à temps partiel comme lecteur dans un département de l'Université hébraïque de Jérusalem en 1994. Il est embauché à l'Université Bar-Ilan, sur l'instigation de Stuart Margolis, professeur à cette université et travaillant sur des sujets voisins, en 1995, soit trois ans après son arrivée[2] - [3].

Ses premiers travaux concernent la théorie des demi-groupes, notamment la question de la base finie, c'est-à-dire la possibilité de définir une variété de demi-groupes par un nombre fini d'identités (aussi connu sous le nom de « problème de Tarski »). À partir du milieu des années 1980, Trahtman s'intéresse à la théorie des automates finis, et étudie en particulier les demi-groupes localement testables associés. Il développe un logiciel appelé TESTAS pour réaliser un certain nombre d'algorithmes qu'il a développés et qui concernent les automates localement testables et ses généralisations et les automates synchronisants. Le package est présenté en 2003[4].

Son intérêt pour les problèmes de coloriage des routes est liée à l'étude de la conjecture de Černy sur la longueur d'un mot synchronisant[5]. Ce problème continue à être central dans ses recherches[6].

En 2007, Trahtman résout le problème du coloriage des routes, un problème de théorie des graphes ouvert 37 ans auparavant, en 1970[7]. Il résout le problème sur 8 pages écrites au crayon à papier[8]. L'article en revue paraît deux ans plus tard[9]. Avraham Trahtman répond affirmativement à la conjecture formulée par Weiss et Adler en 1970 décrivant la classe des graphes possédant un coloriage dit synchronisant. Il a ensuite aussi proposé un algorithme polynomial[10], en temps cubique en fonction du nombre de sommets du graphe, pour calculer un coloriage. Les deux problèmes font l'objet d'un traitement en profondeur dans un chapitre de Béal et Perrin du livre Combinatorics, automata and number theory[11]. Le problème du mot synchronisant continue à faire l'objet d'études.

• Publications de Trahtman sur DBLP
• Page de Trahtman sur le site de l'Université Bar-Ilan