Skip to main content

Research Repository

Advanced Search

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

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

Authors

M. Karpinski

M. Dyer



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
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.