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

Simple item page
dc.creatorBordewich, Magnus
dc.creatorDyer, Martin
dc.creatorKarpinski, Marek
dc.date2005-01-06
dc.date2005-04-02
dc.date.accessioned2026-07-07T05:15:52Z
dc.date.available2026-07-07T05:15:52Z
dc.descriptionWe 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.
dc.descriptionSimpler proof of main theorem. Improved bound on mixing time. 19 pages
dc.identifierhttps://arxiv.org/abs/math/0501081
dc.identifierhttp://arxiv.org/abs/math/0501081
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/73781
dc.subjectProbability
dc.subject60J10; 60C05
dc.titlePath Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
dc.typetext

Files

Collections

arXiv