Avraham Trahtman

Un article de Wikipédia, l'encyclopédie libre.
Avraham Trahtman
Description de l'image Abram 008.jpg.

Naissance (80 ans)
Kalinovo, Nevyansk, Oblast de Sverdlovsk
Nationalité Drapeau d’Israël Israël
Résidence Jérusalem, Israël
Domaines Mathématiques
Institutions Université Bar-Ilan
Directeur de thèse Lev Shevrin
Renommé pour résolution du problème de coloration des graphes

modifier Consultez la documentation du modèle

Avraham Trahtman (Trakhtman) (russe : Абрам Наумович Трахтман) est un mathématicien, chercheur à l'Université Bar-Ilan (Israël), né le à Kalinovo, dans le district de Nevyansk (Oblast de Sverdlovsk). Il est renommé pour avoir résolu le problème du coloriage des routes.

Biographie[modifier | modifier le code]

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].

Travaux[modifier | modifier le code]

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.

Références[modifier | modifier le code]

  1. ↑ (en) « Avraham Trahtman », sur le site du Mathematics Genealogy Project.
  2. ↑ (en) John J. O'Connor et Edmund F. Robertson, « Avraham Naumovich Trahtman », sur MacTutor, université de St Andrews.
  3. ↑ William L. Hosch, « Avraham Trahtman », Encyclopedia Britannica.
  4. ↑ Avraham N. Trahtman, « A Package TESTAS for Checking Some Kinds of Testability », dans Conference Implementation and Application of Automata. CIAA 2002. (no 2608), (ISSN 0302-9743, DOI 10.1007/3-540-44977-9_22), p. 228–232.
  5. ↑ Avraham N. Trahtman, « The Cerny Conjecture for Aperiodic Automata », Discrete Mathematics & Theoretical Computer Science, vol. 9, no 2,‎ , p. 3-10 (HAL hal-00966534, lire en ligne).
  6. ↑ François Gonze, Raphaël M. Jungers et Avraham N. Trahtman, « A Note on a Recent Attempt to Improve the Pin-Frankl Bound », Discrete Mathematics and Theoretical Computer Science, DMTCS, vol. 17, no 1,‎ 307-308 (HAL hal-01196844, lire en ligne, consulté le ).
  7. ↑ Jean-Éric Pin, « On two combinatorial problems arising from automata theory », Annals of Discrete Math., vol. 17,‎ , p. 535-548.
  8. ↑ (en) « MATHEMATICIAN SOLVES BAFFLING 38-YEAR-OLD RIDDLE », sur Tampa Bay Times, (consulté le )
  9. ↑ Avraham N. Trahtman, « The road coloring problem », Israel Journal of Mathematics, vol. 172, no 1,‎ , p. 51–60 (DOI 10.1007/s11856-009-0062-5, arXiv 0709.0099).
  10. ↑ Avraham N. Trahtman, « An algorithm for road coloring », Journal of Discrete Algorithms, vol. 16,‎ , p. 213–223 (DOI 10.1016/j.jda.2012.05.003).
  11. ↑ Marie-Pierre Béal et Dominique Perrin, chap. 7 « Synchronised automata », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, automata and number theory, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (no 135), (ISBN 978-0-521-51597-9, 9781139924733 et 9781107077027, DOI 10.1017/cbo9781139924733.008, présentation en ligne), p. 213-240.

Liens externes[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Avraham_Trahtman&oldid=199726692 ».