Systematic scan for sampling colorings (Q2494577)

The systematic scan for some spin system is studied. The most part of the paper is devoted to proper \(q\)-colorings of a path of \(n\) vertices (the one-dimensional \(q\)-state Potts model at zero temperature). Tight (i.e., matching within a constant factor) upper and lower bounds on mixing time are provided. Measuring mixing time in terms of the number of updates of individual vertices (so that one scan equal to \(n\) updates), the authors show that when \(q=3,\) mixing occurs in \(\Theta(n^3\log n)\) updates, whether Glauber dynamics or systematic scan is used; while when \(q\geq 4\), mixing occurs in \(\Theta(n\log n)\) updates, again independently of whether Glauber or scan is used. Also for ``\(H\)-colorings'' model arbitrary spin systems with symmetric ``hard'' constraints it is shown that for any \(H\), Glauber mixes in \(O(n^5)\) updates and scan in \(O(n^6)\) updates.