Avraham Trahtman

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^[5].

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^[6]. Ce problème continue à être central dans ses recherches^[7].

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^[8]. Il résout le problème sur 8 pages écrites au crayon à papier^[9]. L'article en revue paraît deux ans plus tard^[10]. 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^[11], 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^[12]. 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

• Portail de la Russie
• Portail d’Israël
• Portail des mathématiques