×

An extension of path coupling and its application to the Glauber dynamics for graph colorings. (English) Zbl 0999.05035

Summary: A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps. The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has \(O(n\log(n))\) mixing time for triangle-free \(\Delta\)-regular graphs if \(k\) colors are used, where \(k\geq (2-\eta)\Delta\), for some small positive constant \(\eta\). This is the first proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of \(k\) in the range \(k\leq 2\Delta\).

MSC:

05C15 Coloring of graphs and hypergraphs
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI