Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2005 Copyright 2005 University of Bonn, Department of Computer Science, Abt. V
85262

10.01.2005

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
Magnus Bordewich, Martin Dyer and Marek Karpinski
[Download PostScript] [Download PDF]

We give a new method for analysing the mixing time of a Markov chain 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-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.

Last Change: 11/05/14 at 10:33:34
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V