Mistura rápida de cadeias de Markov em 3 cores de um ciclo

A dinâmica de Glauber é uma cadeia de Markov nas cores de um gráfico, na qual a cada passo tenta-se recolorir um vértice escolhido aleatoriamente com uma cor aleatória. Ele não se mistura para as 3 cores de um ciclo de 5: existem 30 3 cores, mas apenas 15 delas podem ser alcançadas por etapas de recoloração de vértice único. De maneira mais geral, pode-se mostrar que não se mistura para três cores de um ciclo n, a menos que n = 4.

A dinâmica da cadeia de Kempe ou Wang-Swendsen-Kotecký é apenas um pouco mais complicada: a cada passo, escolhe-se um vértice aleatório v e uma cor aleatória c, mas depois encontra-se o subgráfico induzido por duas das cores (c e a cor de v) e troca essas cores no componente que contém v. Não é difícil ver que, diferentemente da dinâmica de Glauber, todas as três cores de um ciclo podem ser atingidas.

A dinâmica de Wang-Swendsen-Kotecký está se misturando rapidamente em três cores de um gráfico de ciclo n-vértice?

Conheço os resultados, por exemplo, por Molloy (STOC 2002), de que Glauber está misturando rapidamente quando o número de cores é pelo menos 1,489 vezes o grau (verdadeiro aqui) e o gráfico a ser colorido tem alta circunferência (também verdadeiro), mas eles também exigem que o grau seja pelo menos logarítmico no tamanho do gráfico (não verdadeiro para gráficos de ciclo), para que eles não se apliquem.

Eu recebi a seguinte solução por e-mail de Dana Randall; portanto, qualquer crédito pela solução deve ser dado a ela (o que eu acho que significa: não vote esta resposta) e quaisquer erros provavelmente foram introduzidos por mim.

A versão curta da solução de Dana é: em vez de usar a cadeia de Markov que descrevi, na qual regiões bicolores potencialmente grandes são recoloridas, use um "banho de calor" no qual removemos repetidamente as cores de dois vértices e depois escolhemos um válido colorindo para eles aleatoriamente. Não é difícil mostrar que, se essa cadeia se mistura, a outra também. Mas um argumento de acoplamento de caminho padrão funciona para mostrar que o banho de calor realmente se mistura.

A versão longa é muito longa para incluir aqui, então eu a coloquei em um post do blog .