ECCC-Report TR05-002https://eccc.weizmann.ac.il/report/2005/002Comments and Revisions published for TR05-002en-usFri, 07 Jan 2005 15:53:53 +0200
Paper TR05-002
| Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs |
Magnus Bordewich,
Martin Dyer,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2005/002We 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.
Fri, 07 Jan 2005 15:53:53 +0200https://eccc.weizmann.ac.il/report/2005/002