Markov-Ketten schnell auf 3-Farben eines Zyklus mischen

Die Glauberdynamik ist eine Markov-Kette auf den Färbungen eines Graphen, bei der bei jedem Schritt versucht wird, einen zufällig ausgewählten Scheitelpunkt mit einer zufälligen Farbe neu einzufärben. Für die 3-Farbtöne eines 5-Zyklus wird nicht gemischt: Es gibt 30 3-Farbtöne, von denen jedoch nur 15 durch Umfärbungsschritte mit einem Scheitelpunkt erreicht werden können. Allgemeiner kann gezeigt werden , dass es sich nicht um 3-Färbungen eines n-Zyklus handelt, es sei denn, n = 4.

Die Kempe - Kette oder die Wang - Swendsen - Kotecký - Dynamik ist nur ein wenig komplizierter: Bei jedem Schritt wählt man einen zufälligen Scheitelpunkt v und eine zufällige Farbe c, aber dann findet man den Teilgraphen, der durch zwei der Farben (c und die Farbe von) induziert wird v) und vertauscht diese Farben innerhalb der Komponente, die v enthält. Es ist nicht schwer zu erkennen, dass im Gegensatz zur Glauberdynamik alle 3-Farben eines Zyklus erreicht werden können.

Vermischt sich die Wang-Swendsen-Kotecký-Dynamik schnell mit 3-Farben eines n-Vertex-Zyklusgraphen?

Ich kenne die Ergebnisse zB von Molloy (STOC 2002), dass Glauber schnell mischt, wenn die Anzahl der Farben mindestens das 1,489-fache des Grades beträgt (hier wahr) und die zu färbende Grafik einen hohen Umfang hat (auch wahr), aber sie auch erfordern, dass der Grad in der Größe des Graphen mindestens logarithmisch ist (gilt nicht für Zyklusgraphen), daher scheinen sie nicht zuzutreffen.

Ich habe die folgende Lösung per E-Mail von Dana Randall erhalten, daher sollte jeder Kredit für die Lösung an sie gehen (was ich vermute, bedeutet: Stimmen Sie dieser Antwort nicht zu), und alle Fehler wurden wahrscheinlich von mir eingeschleppt.

Die Kurzversion von Danas Lösung lautet: Anstatt die von mir beschriebene Markov-Kette zu verwenden, in der potenziell große, zweifarbige Bereiche neu eingefärbt werden, verwenden Sie ein "Wärmebad", in dem wir wiederholt die Farben zweier Scheitelpunkte entfernen und dann einen gültigen auswählen Färbung für sie nach dem Zufallsprinzip. Es ist nicht schwer zu zeigen, dass, wenn sich diese Kette mischt, auch die andere dies tut. Es hat sich jedoch herausgestellt, dass ein Standardargument für die Pfadkopplung zeigt, dass sich das Wärmebad tatsächlich mischt.

Die lange Version ist zu lang, um hier aufgenommen zu werden, daher habe ich sie stattdessen in einen Blog-Post gestellt .