Mencampur rantai Markov dengan cepat pada 3-warna siklus

Dinamika Glauber adalah rantai Markov pada pewarnaan grafik di mana pada setiap langkah seseorang mencoba untuk mewarnai ulang sebuah simpul yang dipilih secara acak dengan warna acak. Itu tidak bercampur untuk 3-warna dari 5-siklus: ada 30 3-warna, tetapi hanya 15 dari mereka yang dapat dicapai dengan langkah-langkah pewarnaan simpul tunggal. Lebih umum, dapat ditunjukkan untuk tidak mencampur 3-warna dari siklus-n kecuali jika n = 4.

Rantai Kempe atau dinamika Wang-Swendsen-Kotecky hanya sedikit lebih rumit: pada setiap langkah seseorang memilih simpul acak v dan warna acak c, tetapi kemudian seseorang menemukan subgraf yang diinduksi oleh dua warna (c dan warna v) dan menukar warna-warna ini dalam komponen yang mengandung v. Tidak sulit untuk melihat bahwa, tidak seperti dinamika Glauber, semua 3-warna dari suatu siklus dapat dicapai.

Apakah dinamika Wang-Swendsen-Kotecký cepat bercampur pada 3-warna dari grafik siklus n-vertex?

Saya tahu hasil misalnya oleh Molloy (STOC 2002) bahwa Glauber cepat mencampur ketika jumlah warna setidaknya 1,489 kali derajat (benar di sini) dan grafik yang akan diwarnai memiliki ketebalan tinggi (juga benar), tetapi mereka juga mengharuskan tingkat setidaknya logaritmik dalam ukuran grafik (tidak berlaku untuk grafik siklus), sehingga mereka tampaknya tidak berlaku.

Saya mendapat solusi berikut ini melalui email dari Dana Randall, jadi kredit apa pun untuk solusi itu harus diberikan kepadanya (yang saya kira artinya: jangan pilih-pilih jawaban ini) dan kemungkinan ada bug yang diperkenalkan oleh saya.

Versi singkat dari solusi Dana adalah: alih-alih menggunakan rantai Markov yang saya jelaskan, di mana daerah dua warna yang berpotensi besar di-recolored, gunakan "penangas panas" di mana kami berulang kali menghapus warna dua simpul dan kemudian memilih yang valid mewarnai untuk mereka secara acak. Tidak sulit untuk menunjukkan bahwa, jika rantai ini bercampur, maka yang lainnya juga. Tetapi argumen kopling jalur standar ternyata berfungsi untuk menunjukkan bahwa pemandian panas memang tercampur.

Versi yang panjang terlalu panjang untuk dimasukkan di sini, jadi saya memasukkannya ke dalam posting blog .