Fast Sampling of b-Matchings and b-Edge Covers

MaRDI QIDQ6434578zbMATH OpenFDO

Authors Zongchen Chen, Yuzhou Gu

Publication date 27 April 2023

Abstract: For integer $bge1$, a $b$-matching (resp. $b$-edge cover) of a graph $G=(V,E)$ is a subset $SsubseteqE$ of edges such that every vertex is incident with at most (resp. at least) $b$ edges from $S$. We prove that for any $bge1$ the simple Glauber dynamics for sampling (weighted) $b$-matchings and $b$-edge covers mixes in $O(nlogn)$ 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 $ble7$ and for $b$-edge covers with $ble2$. Moreover 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 Glauber dynamics from spectral independence.

This page was built for publication: Fast Sampling of $b$-Matchings and $b$-Edge Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6434578)