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: 1133
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