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

17

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

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

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

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

Дэвид Эппштейн
источник

Ответы:

3

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

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

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

Дэвид Эппштейн
источник