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.