Быстрое перемешивание цепей Маркова по 3 раскраскам цикла

Динамика Глаубера - это марковская цепочка на раскрасках графа, в которой на каждом шаге пытаются перекрасить случайно выбранную вершину в случайный цвет. Он не смешивается для 3-х раскрасок из 5-ти циклов: существует 30 3-раскрасок, но только 15 из них могут быть достигнуты с помощью шагов перекраски с одной вершиной. В более общем смысле, можно показать, что не смешиваются для 3-х раскрасок n-цикла, если только n = 4.

Цепочка Кемпе или динамика Ван-Свендсена-Котецки лишь немного сложнее: на каждом шаге выбирают случайную вершину v и случайный цвет c, но затем находят подграф, индуцированный двумя цветами (c и цветом v) и меняет эти цвета внутри компонента, содержащего v. Нетрудно видеть, что, в отличие от динамики Глаубера, могут быть достигнуты все 3 раскраски цикла.

Быстро ли смешивается динамика Ван-Свендсена-Котецки на 3-раскрасках графа цикла из n вершин?

Я знаю о результатах, например, Моллой (STOC 2002), что Глаубер быстро смешивается, когда количество цветов по меньшей мере в 1,489 раз превышает градус (верно здесь), а окрашиваемый график имеет высокий обхват (также верно), но они также Требовать, чтобы степень была по крайней мере логарифмической по размеру графика (не верно для циклических графов), чтобы они не применялись.

Я получил следующее решение по электронной почте от Даны Рэндалл, так что любой кредит за решение должен идти к ней (что, я думаю, означает: не голосуйте против этого ответа), и любые ошибки, вероятно, были внесены мной.

Краткая версия решения Даны такова: вместо использования описанной мной цепочки Маркова, в которой потенциально большие двухцветные области перекрашиваются, используйте «горячую ванну», в которой мы неоднократно удаляем цвета двух вершин, а затем выбираем действительные раскраска для них наугад. Нетрудно показать, что если эта цепочка смешивается, то и другая тоже. Но стандартный аргумент связи между путями, оказывается, работает, чтобы показать, что тепловая ванна действительно смешивается.

Длинная версия слишком длинна, чтобы включить ее здесь, поэтому я поместил ее в блоге .