Path coupling using stopping times

Bordewich, Magnus; Dyer, Martin; Karpinski, Marek

doi:10.1007/11537311_3

Path coupling using stopping times

Bordewich, Magnus; Dyer, Martin; Karpinski, Marek

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

Martin Dyer

Marek Karpinski

Contributors

Maciej Liśkiewicz
Editor

Rüdiger Reischuk
Editor

Abstract

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree Δ of a vertex and the minimum size m of an edge satisfy m ≥ 2Δ +1. We also state results that the Glauber dynamics for proper q-colourings of a hypergraph mixes rapidly if m ≥ 4 and q > Δ, and if m = 3 and q ≥1.65Δ. We give related results on the hardness of exact and approximate counting for both problems.

Citation

Bordewich, M., Dyer, M., & Karpinski, M. (2005). Path coupling using stopping times. In M. Liśkiewicz, & R. Reischuk (Eds.), Fundamentals of computation theory : 15th International Symposium, FCT 2005, 17-20 August 2005, Lübeck, Germany ; proceedings (19-31). https://doi.org/10.1007/11537311_3

Conference Name	15th International Symposium Fundamentals of Computation Theory : FCT 2005.
Conference Location	Lubeck, Germany
Start Date	Aug 17, 2005
End Date	Aug 20, 2005
Publication Date	Aug 1, 2005
Deposit Date	Oct 30, 2008
Pages	19-31
Series Title	Lecture notes in computer science
Series Number	3623
Series ISSN	0302-9743,1611-3349
Book Title	Fundamentals of computation theory : 15th International Symposium, FCT 2005, 17-20 August 2005, Lübeck, Germany ; proceedings.
DOI	https://doi.org/10.1007/11537311_3
Keywords	Hypergraph, Graph colouring, Independent set.
Public URL	https://durham-repository.worktribe.com/output/1162423
Additional Information	17-20 August 2005