Road Coloring Theorem : cas particuliers.

Dans les années 70, Adler, Goodwyn et Weiss ont formulé une conjecture importante "The Road Coloring Conjecture", initialement dans le cadre de la dynamique symbolique mais qui s'exprime naturellement en terme de graphes et d'automates. Soit G un graphe orienté dont tous les sommets ont le même degré sortant k, on considère alors les colorations des arcs avec k couleurs telles que les arcs sortants de chaque sommet utilisent les k couleurs. Une telle coloration est alors dite synchronisante si pour tout sommet "destination" v, il existe une suite finie de couleurs telle que, en partant de tout sommet du graphe et en suivant les arcs indiqués par la suite de couleurs, le chemain se termine toujours sur v. D'autre part, un graphe G est dit apériodique si le PGCD de tous ces circuits vaut 1.

Road Coloring Conjecture : soit G un graphe orienté dont tous les sommets ont le même degré sortant, alors G admet une coloration synchronisante si et seulement si G est fortement connexe et apériodique.

En 2007, A. Trahtman a donné une démonstration de cette conjecture, qui contre toute attente est plutôt très courte (l'article de Trahtman avec cette démonstration est téléchargeable sur le site d'archivage arXiv, il a été publié en 2009 dans un journal scientique). On parle donc maintenant du Road Coloring Theorem. Trahtman utilise quelques notions et résultats courts qui avaient été introduits par de précédents auteurs comme Friedman, Culik, Karhumaki ou Kari et qui avaient déjà permis de traiter des cas particuliers.

Présenter la totalité de la preuve de Trahtman est peut être un objectif un peu long pour en faire un sujet, même si son article est court. Ceci dit plusieurs points sont abordables et le sujet général consiste à présenter le théorème du Road Coloring en étudiant par exemple des cas particuliers plus simples. Voici quelques suggestions :

Quelques références (pas exhaustif).

Retour à la page des sujets.