Fast Sampling of b-Matchings and b-Edge Covers

For an integer b ≥ 1, a b-matching (resp. b-edge cover) of a graph G = (V, E) is a subset S ⊆ E of edges such that every vertex is incident with at most (resp. at least) b edges from S. We prove that for any b ≥ 1 the simple Glauber dynamics for sampling (weighted) b-matchings and b-edge covers mixes in O(n log n) time on all n-vertex bounded-degree graphs. This significantly improves upon previous results which have worse running time and only work for b-matchings with b ≤ 7 and for b-edge covers with b ≤ 2.

More generally, we prove spectral independence for a broad class of binary symmetric Holant problems with log-concave signatures, including b-matchings, b-edge covers, and antiferromagnetic 2-spin edge models. We hence deduce optimal mixing time of the Glauber dynamics from spectral independence.

The core of our proof is a recursive coupling inspired by [CZ23] which upper bounds the Wasserstein W 1 distance between distributions under different pinnings. Using a similar method, we also obtain the optimal O(n log n) mixing time of the Glauber dynamics for the hardcore model on n-vertex bounded-degree claw-free graphs, for any fugacity λ. This improves over previous works which have at least cubic dependence on n.