Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-002 | 6th January 2005 00:00

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

RSS-Feed




TR05-002
Authors: Magnus Bordewich, Martin Dyer, Marek Karpinski
Publication: 7th January 2005 15:53
Downloads: 2933
Keywords: 


Abstract:

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 \Delta of a vertex
and the minimum size m of an edge satisfy m\geq 2\Delta+1. We also show
that the Glauber dynamics for proper q-colourings of a hypergraph mixes
rapidly if m\geq 4 and q > \Delta, and if m=3 and q\geq1.65\Delta.
We give related results on the hardness of exact and approximate counting
for both problems.



ISSN 1433-8092 | Imprint