𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A more rapidly mixing Markov chain for graph colorings

✍ Scribed by Martin Dyer; Catherine Greenhill

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
351 KB
Volume
13
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We define a new Markov chain on proper k-colorings of graphs, and relate its convergence properties to the maximum degree ⌬ of the graph. The chain is shown to have bounds on convergence time appreciably better than those for the well-known JerrumrSalas᎐Sokal chain in most circumstances. For the case k s 2⌬, we provide a dramatic decrease in running time. We also show improvements whenever the graph is regular, or fewer than 3⌬ colors are used. The results are established using the method of path coupling. We indicate that our analysis is tight by showing that the couplings used are optimal in a sense which we define.

πŸ“œ SIMILAR VOLUMES

Very rapidly mixing Markov chains for 2Ξ”
Very rapidly mixing Markov chains for 2Ξ”-colorings and for independent sets in a graph with maximum degree 4
✍ Michael Molloy πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 140 KB πŸ‘ 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A

A semidefinite bound for mixing rates of
A semidefinite bound for mixing rates of Markov chains
✍ Nabil Kahale πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 214 KB πŸ‘ 1 views

We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log 2 n, where n is the number of s