22.11.2005

In this paper we examine the importance of the choice of metric in path coupling,and the relationship of this to stopping time analysis. We give strongevidence that stopping time analysis is no more powerful than standard pathcoupling. In particular, we prove a stronger theorem for path coupling withstopping times, using a metric which allows us to restrict analysis to standardone-step path coupling. This approach provides insight for the design ofnon-standard metrics giving improvements in the analysis of specific problems.
We give illustrative applications to hypergraph independent sets and SAT instances,hypergraph colourings and colourings of bipartite graphs. In particular we proverapid mixing for Glauber dynamics on independent sets in hypergraphs whenever theminimum edge size m and degree Δ satisfy m ≥ Δ + 2,and for all edge sizes when Δ = 3. Previously rapid mixing was only known form ≥ 2Δ + 1. This result leads to approximation schemes for monotoneSAT formulae in which the maximum number of occurrences of a variable (Δ) andthe minimum number of variables per clause (m) satisfy the same condition.For Glauber dynamics on proper colourings of 3-uniform hypergraphs we prove rapidmixing whenever the number of colours q is at least⌈3/2Δ + 1⌉ . Previously the best known result was forq ≥ 1.65Δ and Δ ≥ Δ₀ for some largeΔ₀. Finally we prove rapid mixing of scan dynamics (where theorder of vertex updates is deterministic) for proper colourings of bipartite graphswhenever q > f(Δ), where f(Δ) → βΔ, asΔ → ∞, and β satisfies 1/βe^1/β=1, (β ≈ 1.76). This gives rapid mixing with fewer colours than Vigoda's11Δ/6 bound [22], whenever Δ ≥ 31, and equals this bound forΔ ≥ 14.