For sink-free orientations in graphs of minimum degree at least $3$, we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{72})\log(n/\varepsilon))$, a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time $O((n/\varepsilon)^2\log(n/\varepsilon))$, where $n$ denotes the number of vertices of the input graph and $0<\varepsilon<1$ is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019).

We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n⁸log n). We use connections between Fuss-Catalan structures to construct a comparison argument with a chain similar to Wilson’s lattice path chain (Wilson 2004).

We present two randomised approximate counting algorithms with Oe(n2−c/ε2) running time for some constant c > 0 and accuracy ε: 1. for the hard-core model with fugacity λ on graphs with maximum degree ∆ when λ = O(∆−1.5−c1) where c1 = c/(2 − 2c); 2. for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2. For the hard-core model, Weitz’s algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when λ = o(∆−2). Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as Zd, but with a running time of the form O (n2ε−2/2c(log n)1/d) where d is the exponent of the polynomial growth and c > 0 is some constant.

We provide a perfect sampling algorithm for the hard-sphere model on subsets of $\mathbb{R}^d$ with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.

We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.