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

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

2005-01-06

arxiv.org/abs/math/0501081v2

Mathematics

Probability

Simpler proof of main theorem. Improved bound on mixing time. 19 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293044