La dynamique de Glauber est une chaîne de Markov sur les colorations d'un graphe dans laquelle à chaque étape on tente de recolorer un sommet choisi au hasard avec une couleur aléatoire. Il ne se mélange pas pour les 3 couleurs d'un cycle de 5: il y a 30 3 couleurs, mais seulement 15 d'entre elles peuvent être atteintes par des étapes de recoloration à un seul sommet. Plus généralement, il peut être démontré qu'il ne se mélange pas pour les 3 colorations d'un cycle n sauf si n = 4.
La chaîne de Kempe ou la dynamique de Wang-Swendsen-Kotecký est seulement un peu plus compliquée: à chaque étape, on choisit un sommet aléatoire v et une couleur aléatoire c, mais ensuite on trouve le sous-graphique induit par deux des couleurs (c et la couleur de v) et échange ces couleurs dans le composant contenant v. Il n'est pas difficile de voir que, contrairement à la dynamique de Glauber, toutes les 3 couleurs d'un cycle peuvent être atteintes.
La dynamique de Wang-Swendsen-Kotecký se mélange-t-elle rapidement sur les 3 colorations d'un graphique de cycle à n sommets?
Je connais les résultats, par exemple de Molloy (STOC 2002), selon lesquels Glauber se mélange rapidement lorsque le nombre de couleurs est au moins 1,489 fois le degré (vrai ici) et que le graphique à colorer a une circonférence élevée (également vrai), mais aussi exigent que le degré soit au moins logarithmique dans la taille du graphique (pas vrai pour les graphiques de cycle), donc ils ne semblent pas s'appliquer.
la source