Mezclando rápidamente cadenas de Markov en 3 colores de un ciclo

17

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.

David Eppstein
fuente

Respuestas:

3

Recibí la siguiente solución por correo electrónico de Dana Randall, por lo que cualquier crédito por la solución debería ir a ella (lo que supongo que significa: no votar en contra de esta respuesta) y es probable que yo haya introducido algún error.

La versión corta de la solución de Dana es: en lugar de usar la cadena de Markov que describí, en la que se vuelven a colorear las regiones de dos colores potencialmente grandes, use un "baño de calor" en el que eliminamos repetidamente los colores de dos vértices y luego elegimos un coloreando para ellos al azar. No es difícil demostrar que, si esta cadena se mezcla, entonces la otra también. Pero un argumento de acoplamiento de ruta estándar funciona para mostrar que el baño de calor se mezcla.

La versión larga es demasiado larga para incluirla aquí, así que la puse en una publicación de blog .

David Eppstein
fuente