2005/01/06 by Magnus Bordewich, Martin Dyer, Bordewich, Magnus +3
Mathematics · #60C05 #60J10 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:60C05 #msc:60J10
paper · pdf · doi:10.48550/arxiv.math/0501081
Simpler proof of main theorem. Improved bound on mixing time. 19 pages
arxiv created 2005/04/02 · arxiv updated 2009/12/01
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>= 2Delta+1. We also show that the Glauber dynamics for proper q-colourings of a hypergraph mixes rapidly if m>= 4 and q > Delta, and if m=3 and q>=1.65Delta. We give related results on the hardness of exact and approximate counting for both problems.