We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal convergence results for arbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter $\lambda \gt 0$; the special case $\lambda =1$ corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing time bounds for the complete $\Delta$-regular tree for all $\lambda$. However, Restrepo, Stefankovic, Vera, Vigoda, and Yang (2014) showed that for sufficiently large $\lambda$ there are bounded-degree trees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a polynomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs of bounded tree-width.

We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) of $O(n)$ for the Glauber dynamics for unweighted independent sets on arbitrary trees. We stress that our results hold for arbitrary trees and there is no dependence on the maximum degree $\Delta$. Interestingly, our results extend (far) beyond the uniqueness threshold which is on the order $\lambda =O(1/\Delta )$. Our proof approach is inspired by recent work on spectral independence. In fact, we prove that spectral independence holds with a constant independent of the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixing results of Chen, Liu, and Vigoda (2021) only apply for bounded-degree graphs. We instead utilize the combinatorial nature of independent sets to directly prove approximate tensorization of variance via a non-trivial inductive proof.

We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disc almost as large as the optimal disc for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim 1/(e \Delta )$). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge sizes strictly greater than $2$. We conjecture that for $k\ge 3$, $k$-uniform linear hypergraphs have a much larger zero-free disc of radius $\Omega (\Delta ^{- \frac{1}{k-1}} )$. We establish this in the case of linear hypertrees.

Random sets with long-range dependence can be generated using a Boolean model with power-law grain sizes. We study thinnings of such Boolean models which have the hard-core property that no grains overlap in the resulting germ‒grain model. A fundamental question is whether long-range dependence is preserved under such thinnings. To answer this question, we study four natural thinnings of a Poisson germ‒grain model where the grains are spheres with a regularly varying size distribution. We show that a thinning which favors large grains preserves the slow correlation decay of the original model, whereas a thinning which favors small grains does not. Our most interesting finding concerns the case where only disjoint grains are retained, which corresponds to the well-known Matérn type-I thinning. In the resulting germ‒grain model, typical grains have exponentially small sizes, but rather surprisingly, the long-range dependence property is still present. As a byproduct, we obtain new mechanisms for generating homogeneous and isotropic random point configurations having a power-law correlation decay.

This paper derives upper and lower bounds to the distribution functions of nearest-neighbour and minimum nearest-neighbour distances between N points generated by a hard-core model on the surface of a sphere. The use of these bounds in statistical inference is discussed.