Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

Bordewich, M.; Karpinski, M.; Dyer, M.

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 show that the Glauber dynamics for proper q-colorings 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., Karpinski, M., & Dyer, M. (2008). Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Random Structures and Algorithms, 32(3), 375-399. https://doi.org/10.1002/rsa.20204

• Journal Article Type: Article
• Publication Date: May 1, 2008
• Deposit Date: Dec 21, 2009
• Journal: Random Structures and Algorithms
• Print ISSN: 1042-9832
• Electronic ISSN: 1098-2418
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 32
• Issue: 3
• Pages: 375-399
• DOI: https://doi.org/10.1002/rsa.20204
• Keywords: Path coupling, Markov chain Monte Carlo, Hypergraph coloring, Hypergraph independent set.
• Public URL: https://durham-repository.worktribe.com/output/1546563