La dinámica de Glauber es una cadena de Markov en los colores de un gráfico en el que en cada paso se intenta cambiar el color de un vértice elegido aleatoriamente con un color aleatorio. No se mezcla para los 3 colores de un ciclo 5: hay 30 colores 3, pero solo se puede llegar a 15 de ellos mediante pasos de recoloración de un solo vértice. Más generalmente, se puede demostrar que no se mezcla para 3 colores de un ciclo n a menos que n = 4.
La cadena de Kempe o la dinámica Wang-Swendsen-Kotecký es solo un poco más complicada: en cada paso se elige un vértice aleatorio vy un color aleatorio c, pero luego se encuentra el subgrafo inducido por dos de los colores (c y el color de v) y cambia estos colores dentro del componente que contiene v. No es difícil ver que, a diferencia de la dinámica Glauber, se pueden alcanzar los 3 colores de un ciclo.
¿La dinámica Wang-Swendsen-Kotecký se está mezclando rápidamente en 3 colores de un gráfico de ciclo de n-vértices?
Sé de los resultados, por ejemplo, por Molloy (STOC 2002) de que Glauber se está mezclando rápidamente cuando el número de colores es al menos 1.489 veces el grado (cierto aquí) y el gráfico a colorear tiene una circunferencia alta (también cierto), pero también requieren que el grado sea al menos logarítmico en el tamaño del gráfico (no es cierto para los gráficos de ciclo), por lo que no parecen aplicarse.
fuente