Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-002 | 6th January 2005 00:00

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

TR05-002
Authors: Magnus Bordewich, Martin Dyer, Marek Karpinski
Publication: 7th January 2005 15:53
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