Szybkie mieszanie łańcuchów Markowa na 3-kolorowych cyklach

Dynamika Glaubera to łańcuch Markowa na kolorach wykresu, w którym na każdym kroku próbuje się pokolorować losowo wybrany wierzchołek o losowym kolorze. Nie miesza się w przypadku 3 kolorów w 5 cyklach: istnieje 30 3 kolorów, ale tylko 15 z nich można osiągnąć za pomocą etapów kolorowania pojedynczego wierzchołka. Mówiąc bardziej ogólnie, można wykazać, że nie mieszają się w przypadku 3-kolorowych barw n-cyklu, chyba że n = 4.

Łańcuch Kempe lub dynamika Wanga-Swendsena-Koteckiego jest tylko trochę bardziej skomplikowana: na każdym kroku wybiera się losowy wierzchołek v i losowy kolor c, ale następnie znajduje się wykres podrzędny wywołany dwoma kolorami (c i kolorem v) i zamienia te kolory w komponencie zawierającym v. Nietrudno zauważyć, że w przeciwieństwie do dynamiki Glaubera, można osiągnąć wszystkie 3-kolory w cyklu.

Czy dynamika Wanga-Swendsena-Koteckiego szybko miesza się na 3-kolorowaniu wykresu cyklu n-wierzchołków?

Wiem o wynikach np. Molloya (STOC 2002), że Glauber szybko się miesza, gdy liczba kolorów jest co najmniej 1,489 razy większa niż stopień (tutaj prawda), a wykres do pokolorowania ma wysoki obwód (również prawda), ale one również wymagają, aby stopień był co najmniej logarytmiczny w wielkości wykresu (nieprawda w przypadku wykresów cyklicznych), więc wydaje się, że nie mają one zastosowania.

Dostałem następujące rozwiązanie pocztą e-mail od Dany Randall, więc wszelkie podziękowania za rozwiązanie powinny być dla niej (co chyba oznacza: nie głosuj na tę odpowiedź) i wszelkie błędy zostały prawdopodobnie przeze mnie wprowadzone.

Krótka wersja rozwiązania Dany brzmi: zamiast korzystać z opisanego przeze mnie łańcucha Markowa, w którym potencjalnie duże dwukolorowe regiony są ponownie kolorowane, użyj „kąpieli cieplnej”, w której wielokrotnie usuwamy kolory dwóch wierzchołków, a następnie wybieramy prawidłowy kolorowanki dla nich losowo. Nietrudno wykazać, że jeśli ten łańcuch się miesza, to drugi również. Ale okazuje się, że standardowy argument sprzęgania ścieżek działa, aby pokazać, że kąpiel cieplna rzeczywiście się miesza.

Długa wersja jest zbyt długa, aby ją tu uwzględnić, dlatego umieściłem ją w poście na blogu .