Path coupling using stopping times

Bordewich, Magnus; Dyer, Martin; Karpinski, Marek

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, August). Path coupling using stopping times. Presented at 15th International Symposium Fundamentals of Computation Theory : FCT 2005., Lubeck, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 15th International Symposium Fundamentals of Computation Theory : FCT 2005.
• Start Date: Aug 17, 2005
• End Date: Aug 20, 2005
• Publication Date: Aug 1, 2005
• Deposit Date: Oct 30, 2008
• Print ISSN: 0302-9743
• 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