]} [1.2 em]1.2 em0 em ∗Hasso Plattner Institute, University of Potsdam,
Potsdam, Germany
{tobias.friedrich, andreas.goebel<EMAIL_ADDRESS>
† Karlsruhe Institute of Technology, Karlsruhe, Germany
<EMAIL_ADDRESS>
‡ Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut
Polytechnique de Paris
<EMAIL_ADDRESS>
# Sampling repulsive Gibbs point processes using random graphs

Tobias Friedrich∗ Andreas Göbel∗ Maximilian Katzmann† Martin S. Krejca‡ Marcus
Pappik∗

###### Abstract

We study computational aspects of repulsive Gibbs point processes, which are
probabilistic models of interacting particles in a finite-volume region of
space. We introduce an approach for reducing a Gibbs point process to the
hard-core model, a well-studied discrete spin system. Given an instance of
such a point process, our reduction generates a random graph drawn from a
natural geometric model. We show that the partition function of a hard-core
model on graphs generated by the geometric model concentrates around the
partition function of the Gibbs point process. Our reduction allows us to use
a broad range of algorithms developed for the hard-core model to sample from
the Gibbs point process and approximate its partition function. This is, to
the extend of our knowledge, the first approach that deals with pair
potentials of unbounded range. We compare the resulting algorithms with
recently established results and study further properties of the random
geometric graphs with respect to the hard-core model.

##  1 Introduction

Gibbs point processes are a tool for modelling a variety of phenomena that can
be described as distributions of random spatial events [6, 36]. Such phenomena
include the location of stars in the universe, a sample of cells under the
microscope, or the location of pores and cracks in the ground (see [37, 45]
for more on applications of Gibbs point processes). In statistical physics,
such point processes are frequently used as stochastic models for gases or
liquids of interacting particles [39].

A Gibbs point process on a finite-volume region $\mathds{V}$ is parameterized
by a fugacity $\lambda$ and a pair potential $\phi$ expressing the
interactions between pairs of points. Every point configuration in the region
is assigned a weight according to the pair interactions $\phi$ between all
pairs of points in the configuration. One can then think of a Gibbs point
process as a Poisson point process of intensity $\lambda$, where the density
of each configuration is scaled proportionally to its weight. The density is
normalized by the partition function, which is the integral of the weights
over the configuration space (see Section 1.1 for a formal definition of the
model). The most famous example of such a process is the _hard-sphere model_ ,
a model of a random packing of equal-sized spheres with radius $r$. The pair
potential in the hard-sphere model defines hard-core interactions, i.e.,
configurations where two points closer than some distance $2r$ have weight
zero, while all other configurations have weight one. In this article, we
consider Gibbs point processes with _repulsive_ potentials, that is, pair
potentials in which adding a point to a configuration does not increase its
weight. The hard-sphere model, for example, does have a repulsive pair
potential, however, we do not restrict ourselves to hard-core potentials and
allow for soft-core interactions.

The two most fundamental algorithmic tasks considered on Gibbs point processes
are to sample from the model and to compute its partition function, which are
closely related. Understanding for which potentials and fugacities these two
tasks are tractable is an ambitious endeavour. Towards this goal, there has
been a plethora of algorithmic results on Gibbs point processes spanning
several decades. Notably, the Markov chain Monte Carlo method was developed
for sampling an instance of the hard-sphere model with 224 particles [32].
Since then, a variety of exact and approximate sampling algorithms for such
point processes have been proposed in the literature, and their efficiency has
been studied extensively both without [19, 22] and with rigorous running time
guarantees [35, 24, 21, 34, 1]. The key objective of rigorous works is to
identify a parameter regime for their respective model for which a randomized
algorithm for sampling and approximating the partition function exists with
running time polynomial in the volume of the region. In addition,
deterministic algorithms for approximating the partition function have also
appeared in the literature [17, 26] with running time quasi-polynomial in the
volume of the region.

This recent flurry of algorithmic results on Gibbs point processes can be
attributed to progress in understanding the computational properties of
discrete spin systems, such as the hard-core model. Within these works, two
main approaches can be identified for transferring insights from discrete spin
systems to Gibbs point processes. The first one, which includes results such
as [23, 34, 1], considers properties proven to hold in discrete spin systems
and translates them to the continuous setting of Gibbs point processes. More
precisely, these works consider the notion of strong spatial mixing, which has
been strongly connected to algorithmic properties of discrete spin systems
[47, 40, 16], and translate it to an analogous notion for Gibbs point
processes to obtain algorithmic results. A common pattern in these works is
that once the parameter regime for which strong spatial mixing holds is
established, one needs to prove from scratch that this implies efficient
algorithms in Gibbs point processes. In addition, the definition of strong
spatial mixing for Gibbs points processes assumes that the pair interactions
of two particles is always of bounded range, i.e., if two particles are placed
at distance greater than some constant $r\in\mathds{R}_{\geq 0}$, they do not
interact with each other.

The second approach, used in [18, 17], is to discretize the model, i.e.,
reduce it to an instance of the hard-core model and then solve the respective
algorithmic problem for the hard-core model. In this case, the algorithmic
arsenal developed over the years for the hard-core model is now readily
available for the instances resulting from this reduction. The main downside
of these approaches is that they only apply to the hard-sphere model, a
special case of bounded-range repulsive interactions.

##### Our contributions.

We introduce a natural approach for reducing repulsive point processes to the
hard-core model. Given an instance $(\mathds{V},\lambda,\phi)$ of such a point
process, we generate a random graph by sampling
$n\in\upTheta\mathopen{}\mathclose{{}\left({\mathds{V}^{2}}}\right)$ point-
vertices independently and uniformly at random in $\mathds{V}$ and by
connecting each pair of points with an edge drawn with an appropriate
probability, which depends on $\phi$. We show that computational properties of
the hard-core model on graphs generated by this model and with an
appropriately scaled fugacity transfer to the originating Gibbs point process.

We first show that the partition function of the hard-core model on these
graphs concentrates around the partition function of the Gibbs point process.
Using existing algorithms for the hard-core model as a black box, our result
immediately yields randomized approximation algorithms for the partition
function of the point process in running time polynomial in the volume of
$\mathds{V}$. Furthermore, we show that sampling an independent set from the
generated hard-core model and returning the positions of its vertices in
$\mathds{V}$ results in an approximate sampler from the distribution of the
Gibbs point process. Our approach, in contrast to all previous algorithmic
work in the literature, does not require the pair potential $\phi$ of the
point process to be of bounded range. This includes various models of interest
in statistical physics, such as the (hard-core) Yukawa model [15, 38], the
Gaussian overlap model [7], the generalized exponential model [5], and the
Yoshida–Kamakura model [48].

Finally, we identify the parameter regime (in terms of $\lambda$ and $\phi$)
for which the generated hard-core instance exhibits strong spatial mixing.
This parameter regime is identical to the best known regime for which
repulsive point processes with bounded-range potentials have strong spatial
mixing [34].

###  1.1 Gibbs point processes

We now formally define the notion of a Gibbs point process. As usual in the
theory of point processes, we assume the underlying space to be a complete,
separable metric space $(\mathds{X},d)$ equipped with the Borel algebra
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ and
a reference measure $\nu$ on $(\mathds{X},\mathcal{B})$ that assigns finite
volume to bounded measurable sets. In this work, we study Gibbs point
processes
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ on
bounded measurable regions $\mathds{V}\subseteq\mathds{X}$ that are
parameterized by a _fugacity_ parameter $\lambda\in\mathds{R}_{\geq 0}$ and a
repulsive (i.e., non-negative), symmetric, measurable _potential function_
$\phi\colon\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$. Such a
process $P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$
is defined by a density with respect to a Poisson point process $Q_{\lambda}$
with intensity $\lambda$ on $\mathds{X}$. For every finite point configuration
$\bm{x}=(x_{1},\dots,x_{k})\in\mathds{V}^{k}$, this density is proportional to
$\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(x_{1},\dots,x_{k}}\right)}$,
where $H$ is the _Hamiltonian_

$H\mathopen{}\mathclose{{}\left(x_{1}\dots,x_{k}}\right)=\sum\nolimits_{\\{i,j\\}\in\binom{[k]}{2}}\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right).$

More precisely, the density can be expressed explicitly as

$\frac{\text{d}P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}}{\text{d}Q_{\lambda}missing}(x_{1},\dots,x_{k})=\frac{\mathds{1}_{\forall
i\in[k]\colon
x_{i}\in\mathds{V}}\cdot\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(x_{1},\dots,x_{k}}\right)}\mathrm{e}^{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}{\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)},$

where the normalizing constant
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ is the
_partition function_

$\displaystyle\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$
$\displaystyle=1+\sum_{k\in\mathds{N}_{\geq
1}}\frac{\lambda^{k}}{k!}\int_{\mathds{V}^{k}}\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(x_{1},\dots,x_{k}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right).$

###  1.2 Randomized reduction to the hard-core model

Our approach is to reduce the problem of sampling from a repulsive Gibbs point
process and approximating its partition function to the analogous problems for
a discrete hard-core model, which we briefly introduce. For an undirected
graph $G=(V,E)$, let
$\mathcal{I}\mathopen{}\mathclose{{}\left(G}\right)\subseteq 2^{V}$ denote the
set of independent sets of $G$. For a vertex activity
$\gamma\in\mathds{R}_{\geq 0}$, the _hard-core model_ on $G$ is a probability
distribution $\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma}\right)}$ on
$\mathcal{I}\mathopen{}\mathclose{{}\left(G}\right)$ that assigns each
independent set $I\in\mathcal{I}\mathopen{}\mathclose{{}\left(G}\right)$ a
probability proportional to
$\gamma^{\mathopen{}\mathclose{{}\left|I}\right|}$. The normalizing constant
of this distribution,
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma}\right)=\sum_{I\in\mathcal{I}\mathopen{}\mathclose{{}\left(G}\right)}\gamma^{\mathopen{}\mathclose{{}\left|I}\right|}$,
is called the _hard-core partition function_ on $G$.

The goal is to reduce the problem of approximate sampling from
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ to
approximate sampling from
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma}\right)}$ and, similarly, to
reduce the problem of approximating
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ to
approximating $Z_{G}\mathopen{}\mathclose{{}\left(\gamma}\right)$ for a
suitably chosen graph $G$ and vertex activity $\gamma$. The advantage of this
approach is that sampling from a hard-core model as well as approximating
hard-core partition functions are well studied problems. Specifically, a
sequence of recent papers [3, 4, 10, 11, 12] established approximate sampling
from $\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma}\right)}$ in
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\mathopen{}\mathclose{{}\left|V}\right|}}\right)$
running time and randomized approximation of
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma}\right)$ in
$\widetilde{\mathrm{O}}\big{(}{\mathopen{}\mathclose{{}\left|V}\right|^{2}}\big{)}$
running time for graphs $G$ with maximum degree $d$ for all $\gamma$ strictly
below the _tree threshold_
$\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d}\right)\coloneqq\frac{\mathopen{}\mathclose{{}\left(d-1}\right)^{d-1}}{\mathopen{}\mathclose{{}\left(d-2}\right)^{d}}$.

Our reduction is inspired by the discretization schemes in [17, 18]. These
approaches are limited to the hard-sphere model (and similar models with hard-
core interactions) in specific regions of Euclidean space. In this setting,
the utilized graph $G$ is essentially a unit-disk graph in $\mathds{V}$. This
procedure comes with two major disadvantages. Firstly, the analysis heavily
depends geometric arguments and is therefore restricted to regions in
Euclidean space that satisfy various requirements. Secondly, it is not obvious
how this technique extends to general repulsive potentials $\phi$ and
especially how to account for soft-core interactions.

We circumvent the above problems by investigating hard-core models on a
suitably chosen family of random graphs. For a bounded measurable region
$\mathds{V}\subseteq\mathds{X}$, let $u_{\mathds{V}}$ denote the uniform
distribution on $\mathds{V}$. That is, for $x\sim u_{\mathds{V}}$, we have
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{x\in
A}}\right]=\frac{\nu\mathopen{}\mathclose{{}\left(A}\right)}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$
for every measurable $A\subseteq\mathds{V}$, and
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{x\notin\mathds{V}}}\right]=0$. For
a repulsive potential $\phi$ and a positive integer $n\in\mathds{N}_{\geq 1}$,
we consider a random-graph model $\zeta^{(n)}_{\mathds{V},\phi}$ on the set of
undirected graphs with vertex set $[n]$, where $\zeta^{(n)}_{\mathds{V},\phi}$
is defined by the following natural procedure to generate a graph:

  1. 1.

For each $i\in[n]$, draw a uniform random point $x_{i}\sim u_{\mathds{V}}$
independently.

  2. 2.

For all $i,j\in[n]$ with $i\neq j$, connect $i$ and $j$ with an edge with
probability
$1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}$
independently.

Readers familiar with graphons might notice that this random-graph model can
be expressed as a graphon-based random graph ($W$-random graph) for a suitably
chosen graphon $W$. We discuss this perspective later in the introduction.
Moreover, we would like to mentioned that a similar graph construction based
on points from a Poisson point process was used in [8] to prove uniqueness of
the infinite-volume Gibbs measure for $\lambda<\frac{1}{C_{\phi}missing}$ via
percolation.

The key property of the graphs from $\zeta^{(n)}_{\mathds{V},\phi}$ is that,
for a suitably chosen vertex activity $\gamma$, their hard-core partition
functions concentrate around
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$. This
property is at the core of our reduction.

######  Theorem 1.1.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra, and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$, and let
$\phi\colon\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a
symmetric repulsive potential. For all $\varepsilon\in(0,1]$, $\delta\in(0,1]$
and $n\geq
4\varepsilon^{-2}\delta^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(4\varepsilon^{-1}}\right)^{2}}\right\\}$,
it holds that, for $G\sim\zeta^{(n)}_{\mathds{V},\phi}$,

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)-\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}\right|\geq\varepsilon\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}}\right]\leq\delta.$

Informally, Theorem 1.1 says that, for
$n\in\upTheta\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}}\big{)}$
and $G\sim\zeta^{(n)}_{\mathds{V},\phi}$, the hard-core partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)$
with
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}$
is strongly concentrated around the partition function of the repulsive Gibbs
point process
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$. In [17,
Proposition $5.8$], it was argued that the partition function of an
unrestricted Poisson point process in a bounded measurable region $\mathds{V}$
of Euclidean space cannot be approximated by the hard-core partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)$
for any graph $G$ on $n$ vertices if
$n\in\mathrm{o}\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}}\big{)}$.
As the unrestricted Poisson point process is a special case of a repulsive
Gibbs point process with constant zero potential, this implies that our
concentration result in Theorem 1.1 is tight in terms of its asymptotic
dependency on the volume
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$.

A remarkable aspect of Theorem 1.1 is the generality in which it holds with
respect to the underlying space $\mathds{X}$. In particular, we do not need
any additional assumptions regarding its geometry. We achieve this by deriving
Theorem 1.1 from a corollary of the Efron–Stein inequality [14]. This
corollary gives a convenient-to-use way for proving concentration of functions
of independent random inputs, given that changing one input of the function
only leads to small relative changes of its output. Using this corollary, we
prove Theorem 1.1 by bounding changes in the hard-core partition function of a
graph that are caused by small alternations of the graph structure. We proceed
by discussing this approach in detail.

#### Proving concentration

We prove Theorem 1.1 in two steps. First, we show that, for
$G\sim\zeta^{(n)}_{\mathds{V},\phi}$ and
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}$,
the expected hard-core partition function
$\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}}\right]$
converges rapidly to the partition function of the point process
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ as $n$
grows. We prove this by fixing
$n\in\upTheta\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}}\big{)}$
sufficiently large and rewriting
$\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}}\right]$
as a sum of expectations. We then relate each of the first $m<n$ terms in that
sum with the corresponding term in
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$, which
requires comparing the expected number of independent sets of size $k\leq m$
in a graph $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ with
$\frac{n^{k}}{k!\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}\int_{\mathds{V}^{k}}\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(\bm{x}}\right)}\text{d}\bm{x}$.
Finally, we argue that all terms of order higher than $m$ can be discarded.

Once convergence of the expectation is established, it remains to prove that
the distribution of the partition functions
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)$
for $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ concentrates around this expectation.
To prove the latter, we derive Corollary 3.3 from the Efron–Stein inequality
[14]. This corollary roughly states that the output of a function $f$ on a
product of probability spaces concentrates around its expectation if $f$
exhibits sufficiently small _relative_ changes when any component of its input
is changed. Similar methods for proving concentration usually require the
output of the function $f$ to exhibit small _absolute_ changes (i.e., $f$ to
be Lipschitz, see [30, 31]), which does not hold in our setting.

To apply this concentration bound, we need to express the partition function
of a graph drawn from $\zeta^{(n)}_{\mathds{V},\phi}$ as a function of
independent random inputs. To this end, we model a random graph
$G\sim\zeta^{(n)}_{\mathds{V},\phi}$ based on $n$ points
$\bm{x}=(x_{i})_{i\in[n]}$, each independently drawn from $u_{\mathds{V}}$,
and $\frac{n(n-1)}{2}$ independent random variables $\bm{y}=(y_{i,j})_{1\leq
i<j\leq n}$, each uniformly distributed on the real interval $[0,1]$. Given
the random vectors $\bm{x}$ and $\bm{y}$, we construct a graph by connecting
vertices $i<j$ by an edge if and only if $y_{i,j}\leq
1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}$. Note
that the resulting graph is distributed according to
$\zeta^{(n)}_{\mathds{V},\phi}$. Thus, we express the hard-core partition
function on the random-graph model $\zeta^{(n)}_{\mathds{V},\phi}$ as a
function $f(\bm{x},\bm{y})$ for $\bm{x}$ and $\bm{y}$ as described above. The
effect of changing a component of $\bm{y}$ is bounded by the relative change
of the hard-core partition function when adding or removing an edge. On the
other hand, the effect of changing a component of $\bm{x}$, say $x_{i}$, is
bounded by considering the change of the hard-core partition function when
altering the neighborhood of a single vertex $i$. Bounding both effects and
applying Corollary 3.3 yields the desired concentration result (Theorem 1.1).

In fact, a similar argument as above applies to a broad class of
antiferromagnetic spin systems on graphon-based random graphs that contains
our application as a special case. We discuss his more general setting after
demonstrating the sampling and approximation results for Gibbs point processes
that can be obtained from Theorem 1.1.

###  1.3 Algorithmic implications

We proceed by showcasing some algorithmic results for repulsive Gibbs point
processes that follow from Theorem 1.1. More specifically, we focus on
$\varepsilon$-approximate sampling from the point process and obtaining a
randomized $\varepsilon$-approximation of the partition function. Formally,
the problem of $\varepsilon$_-approximate sampling_ from
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
defined as producing a random point configuration with a distribution that has
a total variation distance of at most $\varepsilon$ to
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$.
Analogously, the problem of $\varepsilon$_-approximating_
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ is
defined as computing some value $x\in\mathds{R}$ such that
$(1-\varepsilon)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\leq
x\leq(1+\varepsilon)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$.
Moreover, an algorithm is called a _randomized_ $\varepsilon$_-approximation_
if it outputs an $\varepsilon$-approximation of
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ with
probability at least $\frac{2}{3}$. The choice of the constant $\frac{2}{3}$
is rather arbitrary here, as the error probability can be made smaller than
every $\delta\in\mathds{R}_{>0}$ by taking the median of
$\mathrm{O}\mathopen{}\mathclose{{}\left({\log\mathopen{}\mathclose{{}\left(\delta^{-1}}\right)}}\right)$
independent runs, as long as the error probability of each run is some
constant smaller than $\frac{1}{2}$. Furthermore, we consider an
$\varepsilon$-approximate sampler and a (randomized)
$\varepsilon$-approximation algorithm as efficient if their running time is
polynomial in the volume $\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$
and in $\varepsilon^{-1}$.

Recent rigorous results establish bounds on the fugacity regime of different
models for which these algorithmic problems can be solved efficiently. Often,
these bounds are stated in terms of the _temperedness constant_ $C_{\phi}$,
which is defined as

$C_{\phi}=\sup_{x_{1}\in\mathds{X}}\int_{\mathds{X}}\mathopen{}\mathclose{{}\left|1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)}}\right|\nu\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right).$

This value can be seen as measure for the strength of interactions between
points.

Given our concentration result (Theorem 1.1), a straightforward idea for
approximating
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ is to
sample a graph $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ and try to approximate its
hard-core partition function. A refined version of this procedure leads to the
following theorem.

######  Theorem 1.2.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra, and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$, and let
$\phi\colon\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a
symmetric repulsive potential. Assume there is a sampler for
$\zeta^{(n)}_{\mathds{V},\phi}$ with running time
$t_{\mathds{V},\phi}\mathopen{}\mathclose{{}\left(n}\right)$.

If $\lambda<\frac{\mathrm{e}missing}{C_{\phi}missing}$, then, for all
$\varepsilon\in(0,1]$, there is a randomized $\varepsilon$-approximation
algorithm for
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ with
running time in
$\widetilde{\mathrm{O}}\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{4}\varepsilon^{-6}}\big{)}+t_{\mathds{V},\phi}\mathopen{}\mathclose{{}\left(\widetilde{\mathrm{O}}\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-2}}\big{)}}\right)$.

With respect to sampling from
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$, it is
less obvious how Theorem 1.1 can be utilized. However, under mild assumptions,
we obtain an approximate sampler, based on Theorem 1.1, by the following
procedure: Sample an independent set
$I\in\mathcal{I}\mathopen{}\mathclose{{}\left(G}\right)$ (approximately) from
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}$
and output the point configuration $\\{x_{i}\\}_{i\in I}$. Given that
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
simple, which means that drawing a point configuration that contains the same
point multiple times has probability zero, a refined version of the approach
sketched above leads to the following result.

######  Theorem 1.3.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra, and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$, and let
$\phi\colon\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a
symmetric repulsive potential. Assume we can sample from the uniform
distribution $u_{\mathds{V}}$ in time $t_{\mathds{V}}$ and, for every
$x,y\in\mathds{V}$, we can evaluate
$\phi\mathopen{}\mathclose{{}\left(x,y}\right)$ in time $t_{\phi}$.

If the Gibbs point process
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
simple and $\lambda<\frac{\mathrm{e}missing}{C_{\phi}missing}$, then, for
every $\varepsilon\in\mathds{R}_{>0}$, there exists an
$\varepsilon$-approximate sampling algorithm for
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ with
running time in
$\widetilde{\mathrm{O}}\big{(}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-4}+\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-3}t_{\mathds{V}}+\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{4}\varepsilon^{-6}t_{\phi}}\big{)}$.

There are two main differences in the assumptions of the approximation result
(Theorem 1.2) and the sampling result (Theorem 1.3). First, the sampling
result requires the point process to be simple. The reason is that, in order
to bound the total variation distance between the output of our sampler and
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$, we
derive a density of that output with respect to a Poisson point process. This
task is greatly simplified by assuming that
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
simple, as it allows for an easier characterization of the output distribution
of our sampling, based on a theorem by Rényi–Mönch (see [13, Theorem
9.2.XII]). However, assuming the point process to be simple is only a minor
restriction, as it is satisfied for most applications of point processes. For
example, it is trivially satisfied if the reference volume measure $\nu$ is
not-atomic (i.e., assigns volume $0$ to single points). This includes the most
frequently studied case of Gibbs point processes in Euclidean space but also a
variety of other spaces, such as Gibbs point processes in hyperbolic spaces or
in Riemannian manifolds.

Second, our sampling result requires efficient sampling from the uniform
distribution $u_{\mathds{V}}$ and an efficient way to compute the potential
$\phi$. In contrast to that, Theorem 1.2 only assumes an efficient way to
sample a graph from $\zeta^{(n)}_{\mathds{V},\phi}$. We state the theorems in
this way to emphasize that, for approximating
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$, we only
need to sample from the random-graph model $\zeta^{(n)}_{\mathds{V},\phi}$.
Our sampling procedure additionally requires the position $x_{i}\in\mathds{V}$
for each vertex $i\in[n]$ along with the graph to output the point
configuration, associated to a random independent set drawn from the hard-core
model.

Last, we briefly discuss the origin of the fugacity bound
$\frac{\mathrm{e}missing}{C_{\phi}missing}$ in our algorithmic results. Write
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}$
for every $n\in\mathds{N}_{\geq 1}$. Note that our algorithms rely on either
an efficient approximation of the hard-core partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)$
or an efficient approximate sampler for an independent set from
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}$
for a random graph $G\sim\zeta^{(n)}_{\mathds{V},\phi}$. As discussed earlier,
such computational results are known for general graphs of maximum degree $d$
as long as the parameter $\gamma$ is below the corresponding tree threshold
$\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d}\right)$. Observe that
$\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d}\right)\approx\frac{\mathrm{e}missing}{dmissing}$
for large $d$. Thus, roughly speaking, we can perform the necessary
computational tasks as long as
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}<\frac{\mathrm{e}missing}{d_{G}missing}$,
where $d_{G}$ is the maximum degree of the graph $G$ that was drawn from
$\zeta^{(n)}_{\mathds{V},\phi}$. Equivalently, this is
$\lambda<\frac{\mathrm{e}n}{d_{G}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$.
The main observation is now that, for $G\sim\zeta^{(n)}_{\mathds{V},\phi}$,
the expected degree of an arbitrary vertex of $G$ is upper-bounded by
$\frac{nC_{\phi}missing}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$.
By proving that, with sufficiently high probability, the maximum degree
$d_{G}$ is not much larger than this value, we obtain the desired bound of
$\frac{\mathrm{e}missing}{C_{\phi}missing}$.

###  1.4 Strong spatial mixing, connective constants, and improved bounds

A property closely tied to the existence of efficient algorithms for the hard-
core model is strong spatial mixing. Strong spatial mixing describes a
particular way how dependencies between distant vertices in a graph $G$ decay.
The definition is easiest stated in terms of the occupation probability of a
vertex $v\in V_{G}$ (i.e., the probability that $v$ is in the independent set,
drawn from a hard-core model on $G$) conditioned on certain vertices being
occupied or unoccupied. Given two such conditions that differ at some vertex
set $S\subset V_{G}$, strong spatial mixing requires that the resulting
difference in the occupation probability of every vertex $v$ is exponentially
small in the graph distance between $v$ and $S$111Often it is more convenient
to work with the occupation ratio, which is the occupation probability divided
by the probability of the vertex to be unoccupied. However, the resulting
strong spatial mixing definitions are equivalent. (see Definition 6.1 and
remark Remark 6.2 for more details).

In a seminal paper, Weitz [47] proved that, for a graph $G$ of maximum degree
$d_{G}$ and vertex $v\in V_{G}$, we can construct a tree with root $v$ such
that the occupation probability of $v$ in the tree is the same as in $G$. This
continues to hold when conditioning on the state of other vertices by
translating the condition to the tree appropriately. It follows that if this
tree exhibits strong spatial mixing with respect to the root, then this
property also holds for $G$. Moreover, in this case, a recursive computation
on this tree can be used to approximate the occupation probability of $v$,
which results in a sampling and approximation algorithm with running time
$\mathopen{}\mathclose{{}\left|V_{G}}\right|^{\mathrm{O}\mathopen{}\mathclose{{}\left({\log(d_{G})}}\right)}$,
for the hard-core model at vertex activity up to
$\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right)$ on $G$.

Subsequently, this result was improved by a more refined analysis [42, 40]. We
elaborate further. The tree used by Weitz, which we refer to as the _Weitz
tree_ , is a truncated version of a self-avoiding walk tree222In [47] the tree
is actually not truncated but certain vertices in the tree are fixed to be
always occupied or unoccupied. However, this is equivalent to truncating the
tree. (see Section 6.3 for a formal definition). This truncation accounts for
the effect of cycles on the hard-core distribution in the original graph. In
[42, 40], it was shown that strong spatial mixing results can be derived by
bounding the connective constant $\Delta$, which describes the growth of the
Weitz tree (see Definition 6.4). In particular, it was shown that strong
spatial mixing applies up to a vertex activity of
$\gamma<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(\Delta}\right)$, which
improves bounds derived from the maximum degree. Consequentially, this implies
sampling and approximation algorithm for the hard-core model for this
parameter regime with running time
$\mathopen{}\mathclose{{}\left|V_{G}}\right|^{\mathrm{O}\mathopen{}\mathclose{{}\left({\log(\Delta)}}\right)}$.

Inspired by these results on the hard-core model, Michelen and Perkins [33]
recently introduced the potential-weighted connective constant $\Delta_{\phi}$
for repulsive Gibbs point processes (see Section 6.1 for a formal definition).
It can be seen as an alternative to $C_{\phi}$ that is more sensitive to the
structure of the underlying space $\mathds{X}$. In particular, for any non-
trivial potential, $\Delta_{\phi}$ is strictly smaller than the temperedness
constant. Moreover, it was shown in [34] that repulsive Gibbs point processes
with bounded-range potentials exhibit a notion of strong spatial mixing up to
a fugacity of $\lambda<\mathrm{e}/\Delta_{\phi}$ (see [34, Definition 1]).
This result was used to derive a polynomial-time approximate sampling
algorithm and a randomized approximation algorithm for the partition function
of bounded-range repulsive Gibbs point processes in the same fugacity regime.

Given a repulsive Gibbs point process with fugacity
$\lambda<\mathrm{e}/\Delta_{\phi}$, we show in Section 6 that the hard-core
model that is obtained from our reduction exhibits strong spatial mixing with
high probability. In particular our result holds without bounded-range
assumptions. We prove this by using the results in [42, 40]. Towards this, we
establish a rigorous connection between the potential-weighted connective
constant of a repulsive Gibbs point process and the connective constant of a
graph from $\zeta^{(n)}_{\mathds{V},\phi}$. More precisely, we show that, for
any $\epsilon>0$ and
$n\geq\upTheta\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}\right)$,
the connective constant of a graph from $\zeta^{(n)}_{\mathds{V},\phi}$ is
bounded by
$\mathrm{e}^{\epsilon}\frac{n}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\Delta_{\phi}$
with probability at least $1-\frac{1}{n}$ (see Theorem 6.7 for the formal
statement). To obtain this result, we make use of the fact that the
construction of the Weitz tree leaves some degree of freedom. That is, for the
same graph $G$ and root vertex $v\in V_{G}$, different Weitz trees can be
constructed, which differ in how the self-avoiding walk tree is truncated. In
our setting, we carefully need to choose the truncation based on the
underlying location of vertices in $\mathds{V}$. In particular, it is
important for us to define the connective constant in terms of the Weitz tree
and not the full self-avoiding walk tree. The latter would only yield a bound
of $\frac{n}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}$,
which would be no improvement over the maximum degree of
$G\sim\zeta^{(n)}_{\mathds{V},\phi}$.

Given the above graphical interpretation of $\Delta_{\phi}$, we immediately
obtain that, for all $\lambda<\mathrm{e}/\Delta_{\phi}$, a hard-core model
with vertex activity
$\gamma(n)=\frac{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}\lambda$
exhibits strong spatial mixing on $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ with
probability at least $1-\frac{1}{n}$ (see Corollary 6.10 for the formal
statement). This result holds for any repulsive potential, without bounded-
range assumption. However, it should be noted that the strong spatial mixing
is with respect to the graph distance and not the distance metric of the
underlying space $\mathds{X}$.

This strong spatial mixing result for $G\sim\zeta^{(n)}_{\mathds{V},\phi}$
gives our reduction further algorithmic consequences. Using the deterministic
algorithm for approximating that partition function of a hard-core model
proposed by Weitz [47] (see also [42, 40]) and Theorem 1.1, our strong spatial
mixing result yields a randomized approximation for the partition function of
repulsive Gibbs point processes with arbitrary range potentials for
$\lambda<\mathrm{e}/\Delta_{\phi}$ with quasi-polynomial running time
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{\mathrm{O}\mathopen{}\mathclose{{}\left({\ln(\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right))}}\right)}$.
A similar result can be derived in the setting of approximate sampling.

###  1.5 A more general concentration result: antiferromagnetic partition
functions on graphon-based random graphs

So far, we discussed how concentration of hard-core partition functions
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
for random graphs $G\sim\zeta^{(n)}_{\mathds{V},\phi}$, stated in Theorem 1.1
is obtained from Corollary 3.3. However, as hinted earlier, a more general
concentration result can be obtained for a large class of antiferromagnetic
two-state spin systems on graphon-based random graph models. As such spin
systems have been studied extensively [28, 41, 43], we believe this result to
be of independent interest. In what follows, we outline this more general
concentration result and show how Theorem 1.1 follows as a special case of it.

We start by introducing the class of spin systems to which it applies. For an
undirected graph $G=(V,E)$ with vertices $V$ and edges
$E\subseteq\binom{V}{2}$, we denote by $\Sigma_{G}$ the set of all functions
$\sigma\colon V\to\\{0,1\\}$. To simplify notation, we assume $V=[n]$ for some
$n\in\mathds{N}$. A _two-state spin system_ with parameters
$\gamma,\beta_{0},\beta_{1}\in\mathds{R}_{\geq 0}$ on $G$ is a probability
distribution
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}$
on $\Sigma_{G}$ with

$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}\mathopen{}\mathclose{{}\left(\sigma}\right)=\frac{\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta_{0}^{m_{G}^{(0)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\beta_{1}^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}}{Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)},$

where
$\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}=\mathopen{}\mathclose{{}\left|\sigma^{-1}(1)}\right|$
counts the number of vertices that are assigned to $1$,
$m_{G}^{(a)}\mathopen{}\mathclose{{}\left(\sigma}\right)=\sum_{\\{i,j\\}\in
E}\mathds{1}_{\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=a}$
counts the number of edges with both endpoints assigned to $a\in\\{0,1\\}$,
and the normalizing constant
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)$ is the
partition function

$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)=\sum\nolimits_{\sigma\in\Sigma_{G}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta_{0}^{m_{G}^{(0)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\beta_{1}^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}.$

A two-state spin system is _antiferromagnetic_ if $\beta_{0}\beta_{1}\leq 1$.
Our concentration result applies to antiferromagnetic two-state spin systems
with $\beta_{0}=1$. In this case, we omit $\beta_{0}$ completely, write
$\beta=\beta_{1}\in[0,1]$, and denote the partition function by
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$.

Our concentration result for partition functions
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$ applies to all
graphon-based random-graph models. Here, we refer to graphons in the most
general sense, as defined in [29, Chapter $13$]. That is, for a probability
space $\mathcal{X}=(X,\mathcal{A},\xi)$, a _graphon_ is a symmetric function
$W\colon X^{2}\to[0,1]$ that is measurable with respect to the product algebra
$\mathcal{A}^{2}=\mathcal{A}\otimes\mathcal{A}$. Note that, even though we
call the function $W$ the graphon, we mean implicitly that a graphon is a
tuple of an underlying probability space and a suitable function $W$. One
useful aspect of a graphon $W$ is that it naturally defines a family of
random-graph models, sometimes called $W$-random graphs (see [29, Chapter
$11$]). For every $n\in\mathds{N}_{\geq 1}$, we denote by $\mathds{G}_{W,n}$ a
distribution on undirected graphs with vertex set $[n]$ that is induced by the
following procedure for generating a random graph:

  1. 1.

Draw a tuple $(x_{1},\dots x_{n})\in X^{n}$ according to the product
distribution $\xi^{n}$.

  2. 2.

For all $i,j\in[n],i\neq j$, add the edge $\\{i,j\\}$ independently with
probability $W\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)$.

Observe that $\mathds{G}_{W,n}$ encompasses classical random-graph models,
such as Erdős–Rényi random graphs and geometric random graphs.

Applying Corollary 3.3 and using essentially the same arguments as in our
proof sketch for Theorem 1.1 yields the following result.

######  Theorem 1.4.

Let $W$ be a graphon on the probability space
$\mathcal{X}=(X,\mathcal{A},\xi)$. Let $\gamma\colon\mathds{N}_{\geq
1}\to\mathds{R}_{\geq 0}$ such that
$\gamma\mathopen{}\mathclose{{}\left(n}\right)\leq\gamma_{0}n^{-\frac{1+\alpha}{2}}$
for some $\gamma_{0}\in\mathds{R}_{\geq 0}$ and $\alpha\in\mathds{R}_{>0}$.
For all $\beta\in[0,1]$, $\varepsilon\in(0,1]$, $\delta\in(0,1]$,
$n\geq\mathopen{}\mathclose{{}\left(2\gamma_{0}^{2}\varepsilon^{-2}\delta^{-1}}\right)^{\frac{1}{\alpha}}$,
and $G\sim\mathds{G}_{W,n}$, it holds that

$\mathrm{Pr}\big{[}{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)-\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\right|\geq\varepsilon\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\big{]}\leq\delta.$

######  Remark 1.5.

In fact, Theorem 1.4 can easily be extended to an even more general setting,
where we consider a sequence of probability spaces
$(\mathcal{X}_{n})_{n\in\mathds{N}}$ and an associated sequence of graphons
$(W_{n})_{n\in\mathds{N}}$ (i.e., each $W_{n}$ is a graphon on
$\mathcal{X}_{n}$). This makes the result for example applicable to popular
models studied in network theory, such as hyperbolic random graphs [27] and
geometric inhomogeneous random graphs [9].

A surprising aspect of Theorem 1.4 is that, even though
$\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]\geq
1+n\gamma\mathopen{}\mathclose{{}\left(n}\right)$ diverges for
$\gamma\mathopen{}\mathclose{{}\left(n}\right)\in\omega(n^{-1})$ as $n$
increases, Theorem 1.4 still ensures that the distribution of the partition
functions gets more and more concentrated as long as
$\gamma\mathopen{}\mathclose{{}\left(n}\right)\in\mathrm{o}\big{(}{n^{-\frac{1}{2}}}\big{)}$.

We derive Theorem 1.1 as a special case of Theorem 1.4. To see how this works,
first observe that, for $\beta=0$, it holds that
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)$
is the hard-core partition function of a graph $G$ with parameter
$\gamma\in\mathds{R}_{\geq 0}$. Moreover, by setting
$\mathcal{X}=(\mathds{V},\mathcal{B},u_{\mathds{V}})$, considering a graphon
$W_{\phi}\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)=1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)}$,
$x_{1},x_{2}\in\mathds{V}$, on $\mathcal{X}$, we obtain
$\zeta^{(n)}_{\mathds{V},\phi}=\mathds{G}_{W_{\phi},n}$. This way of
expressing $\zeta^{(n)}_{\mathds{V},\phi}$ establishes a connection between
repulsive Gibbs point processes and hard-core models on graphon-based random
graphs. Lastly, setting
$\gamma_{0}=\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$ and
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\gamma_{0}n^{-1}$ and applying
Theorem 1.4 yields the desired concentration result for hard-core partition
functions on $\zeta^{(n)}_{\mathds{V},\phi}$.

###  1.6 Organization of the technical details

The technical details in the appendix are organized as follows. In Section 2,
we formally introduce the notion of antiferromagnetic spin systems and Gibbs
point processes. Note that for the latter one, we base our definition on the
notion of random counting measures. This is common in the theory of point
processes but slightly differs from the definition given in the introduction.
In Section 3, we prove our concentration result for partition functions of
antiferromagnetic spin systems on graphon-based random graphs. We continue by
showing in Section 4 how to efficiently approximate the partition functions of
a Gibbs point process with arbitrary repulsive potentials via hard-core
partition functions of random graphs based on a suitably constructed graphon.
In Section 5, we show how a similar approach can be used to obtain an
approximate sampler for repulsive Gibbs point processes. Finally, in Section 6
we give a high-probability bound on the connective constant of the graphs
obtained from our reduction and derive corresponding strong spatial mixing
results.

##  2 Preliminaries

We formally introduce the discrete antiferromagnetic spin systems we
investigate, as well as Gibbs point processes.

###  2.1 Antiferromagnetic spin systems

For an undirected graph $G=(V,E)$ with vertices $V$ and edges
$E\subseteq\binom{V}{2}$, we denote by $\Sigma_{G}$ the set of all functions
$\sigma:V\to\\{0,1\\}$. Without loss of generality, we are going to assume the
canonical vertex set $V=[n]$ for some $n\in\mathds{N}$. A _two-state spin
system_ with parameters $\gamma,\beta_{0},\beta_{1}\in\mathds{R}_{\geq 0}$ on
$G$ is a probability distribution
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}$
on $\Sigma_{G}$ with

$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}\mathopen{}\mathclose{{}\left(\sigma}\right)=\frac{\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta_{0}^{m_{G}^{(0)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\beta_{1}^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}}{Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)},$

where
$\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}=\mathopen{}\mathclose{{}\left|\sigma^{-1}(1)}\right|$
counts the number of vertices assigned that are to $1$,
$m_{G}^{(a)}\mathopen{}\mathclose{{}\left(\sigma}\right)=\sum_{\\{i,j\\}\in
E}\mathds{1}_{\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=a}$
counts the number of edges with both endpoints assigned to $a\in\\{0,1\\}$ and
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)$ is the
normalizing constant

$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)=\sum_{\sigma\in\Sigma_{G}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta_{0}^{m_{G}^{(0)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\beta_{1}^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}.$

Note that we implicitly assume $\beta_{0}\neq 0$ or $\beta_{1}\neq 0$, as
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}$
may not be defined otherwise.

Usually,
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma,\beta_{0},\beta_{1}}\right)}$
is referred to as the _Gibbs distribution_ of the model and $Z_{G}$ is called
the _partition function_. Further, a two-state spin system is
_antiferromagnetic_ if $\beta_{0}\beta_{1}\leq 1$. For our concentration
result, we focus on the setting where $\beta_{0}=1$. In this case, we omit
$\beta_{0}$ completely and write $\beta=\beta_{1}\in[0,1]$ and denote the
partition function by
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$. Of special interest
within this class of antiferromagnetic two-state spin systems in the _hard-
core model_ , which results from setting $\beta=0$. In this case, we might
just omit the edge interactions $\beta$ completely and write
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma}\right)}$ and
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma}\right)$. Note that this implies
that only configurations $\sigma\in\Sigma_{G}$ for which $\sigma^{-1}(1)$ is
an independent set in $G$ can have non-zero probability. For us, this model is
especially relevant, as we show that concentration of hard-core partition
functions on random graphs can be used to derive randomized approximations for
the partition function of repulsive Gibbs point processes, which are
introduced in the next section.

###  2.2 Gibbs point processes

We introduce the notion of Gibbs point processes that is used throughout this
paper. For a formal treatment, it is common to model point processes as random
counting measures. Note that this is different from the simplified definition
that we gave in the introduction. For a more detailed overview on the theory
of point processes and specifically Gibbs point processes, see [25].

Let $(\mathds{X},d)$ be a complete, separable metric space and let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra of that space. Let $\nu$ be a locally finite reference
measure on $(\mathds{X},\mathcal{B})$ such that all bounded measurable sets
have finite measure. Denote by $\mathcal{N}$ the set of all locally finite
counting measures on $(\mathds{X},\mathcal{B})$. Formally, this is the set of
all measures $\eta$ on $(\mathds{X},\mathcal{B})$ with values in
$\mathds{N}\cup\\{\infty\\}$ such that
$\nu\mathopen{}\mathclose{{}\left(A}\right)<\infty$ implies
$\eta\mathopen{}\mathclose{{}\left(A}\right)<\infty$ for all
$A\in\mathcal{B}$. For each $A\in\mathcal{B}$, define a map
$N_{A}:\mathcal{N}\to\mathds{N}\cup\\{\infty\\}$ with
$\eta\mapsto\eta\mathopen{}\mathclose{{}\left(A}\right)$ and let $\mathcal{R}$
be the sigma algebra on $\mathcal{N}$ that is generated by the set of those
maps $\\{N_{A}\mid A\in\mathcal{B}\\}$. A _point process_ on $\mathds{X}$ is
now a measurable map from some probability space to the measurable space
$(\mathcal{N},\mathcal{R})$. With some abuse of terminology, we call any
probability distribution on $(\mathcal{N},\mathcal{R})$ a point process, as we
can only use the identity as measurable mapping from $\eta$ to itself.
Moreover, a point process is call _simple_ if
$N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)\leq 1$ with probability $1$,
where we write $N_{x}$ for $N_{\\{x\\}}$.

Note that every counting measure $\eta\in\mathcal{N}$ is associated with a
multiset of points in $\mathds{X}$. To see this, define
$X_{\eta}=\\{x\in\mathds{X}\mid
N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)>0\\}$. Then $\eta$ can be
expressed as a weighted sum of Dirac measures

$\eta=\sum_{x\in
X_{\eta}}N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)\delta_{x}.$

In this sense, $\eta$ is associated with a multiset of points $x\in X_{\eta}$,
each occurring with finite multiplicity
$N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)$. We may use such a _point
configuration_ interchangeably with its corresponding counting measure.

An important example for point processes are Poisson point processes. A
_Poisson point process_ with intensity $\kappa\in\mathds{R}_{\geq 0}$ on
$(\mathds{X},d)$ is uniquely defined by the following properties

  * •

for all bounded measurable $A\subseteq\mathds{X}$ it holds that $N_{A}$ is
Poisson distributed with intensity
$\kappa\nu\mathopen{}\mathclose{{}\left(A}\right)$ and

  * •

for all $m\in\mathds{N}_{\geq 2}$ and disjoint measurable
$A_{1},\dots,A_{m}\subseteq\mathds{X}$ it holds that
$N_{A_{1}},\dots,N_{A_{m}}$ are independent.

Generally speaking, a _Gibbs point process_ is a point process that is
absolutely continuous with respect to a Poisson point process. For a bounded
measurable $\mathds{V}\subseteq\mathds{X}$ let $\mathcal{N}_{\mathds{V}}$
denote the set of locally finite counting measures $\eta\in\mathcal{N}$ that
satisfy $N_{A}\mathopen{}\mathclose{{}\left(\eta}\right)=0$ for all measurable
$A\subseteq\mathds{X}\setminus\mathds{V}$. In this work we are interested in
Gibbs point processes
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ on
bounded measurable regions $\mathds{V}\subseteq\mathds{X}$ that are
parameterized by a _fugacity_ parameter $\lambda\in\mathds{R}_{\geq 0}$ and
non-negative, symmetric, measurable _potential function_
$\phi:\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$. Formally, such a
process $P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$
is defined by having a density with respect to a Poisson point process with
intensity $\lambda$ of the form

$\frac{\text{d}P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}}{\text{d}Q_{\lambda}missing}(\eta)=\frac{\mathds{1}_{\eta\in\mathcal{N}_{\mathds{V}}}\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(\eta}\right)}\mathrm{e}^{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}{\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$

where $H:\mathcal{N}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ is the
_Hamiltonian_ defined by

$H\mathopen{}\mathclose{{}\left(\eta}\right)=\sum_{\\{x,y\\}\in\binom{X_{\eta}}{2}}N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)N_{y}\mathopen{}\mathclose{{}\left(\eta}\right)\phi\mathopen{}\mathclose{{}\left(x,y}\right)+\sum_{x\in
X_{\eta}}\frac{N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)(N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)-1)}{2}\phi\mathopen{}\mathclose{{}\left(x,x}\right).$

The normalizing constant
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ is
usually called the _(grand-canonical) partition function_ and can be written
explicitly as

$\displaystyle\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$
$\displaystyle=1+\sum_{k\in\mathds{N}_{\geq
1}}\frac{\lambda^{k}}{k!}\int_{\mathds{V}^{k}}\mathrm{e}^{-H\mathopen{}\mathclose{{}\left(\delta_{x_{1}}+\dots+\delta_{x_{k}}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=1+\sum_{k\in\mathds{N}_{\geq
1}}\frac{\lambda^{k}}{k!}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right).$

##  3 Concentration of partition functions of antiferromagnetic spin systems
on graphon-based random graphs

The main tool we will use to derive our concentration bounds is the
Efron–Stein inequality. For $N\in\mathds{N}_{\geq 1}$ let
$\\{(\Omega_{i},\mathcal{F}_{i},\mu_{i})\\}_{i\in[N]}$ be a collection of
probability spaces and let $f:\Omega\to\mathds{R}$ be a measurable function on
the product space
$(\Omega,\mathcal{F},\mu)=\bigotimes_{i\in[N]}(\Omega_{i},\mathcal{F}_{i},\mu_{i})$.
For each $i\in[N]$ define a function
$\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}:\Omega\times\Omega_{i}\to\mathds{R}_{\geq
0}$, where, for every $\bm{x}=(x_{1},\dots,x_{N})\in\Omega$ and
$y_{i}\in\Omega_{i}$, the value
$\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}\mathopen{}\mathclose{{}\left(\bm{x},y_{i}}\right)$
is defined as the squared difference in $f$ that is caused by replacing
$x_{i}$ in $\bm{x}$ with $y_{i}$. Formally, this is
$\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}\mathopen{}\mathclose{{}\left(\bm{x},y_{i}}\right)=(f(\bm{x})-f(\bm{y}))^{2}$
where $\bm{y}=(x_{1},\dots,x_{i-1},y_{i},x_{i+1},\dots,x_{N})$. The
Efron–Stein inequality bounds the variance of $f$ under $\mu$ based on the
local squared deviations
$\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}\mathopen{}\mathclose{{}\left(\bm{x},y_{i}}\right)$.

######  Theorem 3.1 (Efron–Stein inequality [14]).

Let $\\{(\Omega_{i},\mathcal{F}_{i},\mu_{i})\\}_{i\in[N]}$ be probability
spaces with product space
$(\Omega,\mathcal{F},\mu)=\bigotimes_{i\in[N]}(\Omega_{i},\mathcal{F}_{i},\mu_{i})$.
For every $\mathcal{F}$-measurable function $f:\Omega\to\mathds{R}$ it holds
that

$\mathrm{Var}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]\leq\frac{1}{2}\sum\nolimits_{i\in[N]}\mathrm{E}_{\mu\times\mu_{i}}\mathopen{}\mathclose{{}\left[{\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}}}\right].$

######  Remark 3.2.

The Efron–Stein inequality is usually stated for functions of independent
real-valued random variables. However, it extends to functions on products of
arbitrary probability spaces.

Theorem 3.1 immediately gives a concentration result for $f$ whenever
$\frac{1}{2}\sum_{i\in[N]}\mathrm{E}_{\mu\times\mu_{i}}\big{[}{\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}}\big{]}$
is of order of magnitude
$\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]^{2}$ by using
Chebyshev’s inequality. However, obtaining such a bound might turn out
difficult, especially if
$\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]$ is hard to compute
explicitly. For our setting, we derive the following corollary of Theorem 3.1.

######  Corollary 3.3.

[Corollary of the Efron–Stein inequality] Let
$\\{(\Omega_{i},\mathcal{F}_{i},\mu_{i})\\}_{i\in[N]}$ be probability spaces
with product space
$(\Omega,\mathcal{F},\mu)=\bigotimes_{i\in[N]}(\Omega_{i},\mathcal{F}_{i},\mu_{i})$,
and let $f\colon\Omega\to\mathds{R}$ be an $\mathcal{F}$-measurable function.
Assume that there are $c_{i}\in\mathds{R}_{\geq 0}$ for $i\in[N]$ such that
$C\coloneqq\sum_{i\in[N]}c_{i}^{2}<2$ and, for all
$\bm{x}=(x_{j})_{j\in[N]}\in\Omega$ and $\bm{y}=(y_{j})_{j\in[N]}\in\Omega$
that disagree only at position $i$, it holds that

$\mathopen{}\mathclose{{}\left|f(\bm{x})-f(\bm{y})}\right|\leq
c_{i}\cdot\min\\{\mathopen{}\mathclose{{}\left|f(\bm{x})}\right|,\mathopen{}\mathclose{{}\left|f(\bm{y})}\right|\\}.$

Then, for all $\varepsilon\in\mathds{R}_{>0}$, it holds that

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|f-\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]}\right|\geq\varepsilon\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]}}\right]\leq\mathopen{}\mathclose{{}\left(\frac{2}{2-C}-1}\right)\frac{1}{\varepsilon^{2}}.$

###### Proof.

First, we observe that
$\mathopen{}\mathclose{{}\left|f(\bm{x})-f(\bm{y})}\right|\leq
c_{i}\min\\{\mathopen{}\mathclose{{}\left|f(\bm{x})}\right|,\mathopen{}\mathclose{{}\left|f(\bm{y})}\right|\\}\leq
c_{i}\mathopen{}\mathclose{{}\left|f(\bm{x})}\right|$ implies
$\mathrm{E}_{\mu\times\mu_{i}}\mathopen{}\mathclose{{}\left[{\Delta_{i}^{\mathopen{}\mathclose{{}\left(f}\right)}}}\right]\leq
c_{i}^{2}\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]$ for
all $i\in[N]$. Thus, by Theorem 3.1, we have
$\mathrm{Var}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]\leq\frac{C}{2}\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]$.
Now, recall that by definition
$\mathrm{Var}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]=\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]-\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]^{2}$,
which implies
$\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]-\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]^{2}\leq\frac{C}{2}\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]$.
Rearranging for
$\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]$ and using the
fact that $\frac{C}{2}<1$ yields
$\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f^{2}}}\right]\leq\frac{2}{2-C}\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]^{2}$.
Substituting this back into the definition of the variance, we obtain

$\mathrm{Var}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]\leq\mathopen{}\mathclose{{}\left(\frac{2}{2-C}-1}\right)\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]^{2}.$

The claim follows immediately by applying Chebyshev’s inequality. ∎

######  Remark 3.4.

Usually, we want to characterize concentration asymptotically in $N$. In this
setting, Corollary 3.3 tells us that, if
$c_{i}\in\mathrm{O}\mathopen{}\mathclose{{}\left({N^{-\frac{1+\alpha}{2}}}}\right)$
for all $i\in[N]$ and some $\alpha>0$, then, for all
$\varepsilon\in\mathds{R}_{>0}$ and $\delta\in(0,1]$ such that
$\varepsilon^{2}\delta<1$, it is sufficient to choose
$N\in\upTheta\mathopen{}\mathclose{{}\left({\delta^{-\frac{1}{\alpha}}\varepsilon^{-\frac{2}{\alpha}}}}\right)$
to ensure

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|f-\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]}\right|\geq\varepsilon\mathrm{E}_{\mu}\mathopen{}\mathclose{{}\left[{f}}\right]}}\right]\leq\delta.$

We are now ready to use Corollary 3.3 and derive a concentration result for
the partition functions of antiferromagnetic two-state spin systems for
graphon-based random graph model.

Let us recall the definition of graphons and graphon-based random graphs that
we are using (see [29, Chapter $10$ & $13$]). Let
$\mathcal{X}=(X,\mathcal{A},\xi)$ be a probability space. A graphon on
$\mathcal{X}$ is a symmetric function $W:X^{2}\to[0,1]$ that is measurable
with respect to the product algebra
$\mathcal{A}^{2}=\mathcal{A}\otimes\mathcal{A}$. For $n\in\mathds{N}_{\geq 1}$
we denote by $\mathcal{G}_{n}$ the set of all graphs on the canonical vertex
set $[n]=\\{1,\dots,n\\}$. Note that each graph in $\mathcal{G}_{n}$ is fully
characterized by its edge set $E$. For every $n\in\mathds{N}_{\geq 1}$ the
random graph model induced by a graphon $W$ on a probability space
$(X,\mathcal{A},\xi)$ is described by generating a random graph $G=([n],E)$ by

  * •

drawing a tuple $(x_{1},\dots x_{n})\in X^{n}$ according to the product
distribution $\xi^{n}$ and

  * •

adding the edge $\\{i,j\\}$ for all $i,j\in[n],i\neq j$ independently with
probability $W\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)$.

Formally, this gives a probability distribution $\mathds{G}_{W,n}$ on
$\mathcal{G}_{n}$ with

$\mathds{G}_{W,n}\mathopen{}\mathclose{{}\left(G}\right)=\bigintsss_{X^{n}}\mathopen{}\mathclose{{}\left(\prod_{\\{i,j\\}\in
E}W\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\right)\cdot\mathopen{}\mathclose{{}\left(\prod_{\\{i,j\\}\in\binom{[n]}{2}\setminus
E}\mathopen{}\mathclose{{}\left(1-W\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\right)}\right)\xi^{n}(\text{d}\bm{x})$

for all $G\in\mathcal{G}_{n}$, where $\bm{x}=(x_{i})_{i\in[n]}$ inside the
integral.

To apply Corollary 3.3 to partition functions on random graphs from
$\mathds{G}_{W,n}$, we will need to bound how much the partition function
changes when applying small modifications to the structure of a graph. More
specifically, we want to get a bound on the relative change of the partition
function, given that we

  * •

add or remove a single edge, or

  * •

add or remove a set of edges that are all incident to the same vertex.

The following two lemmas provide such bounds.

######  Lemma 3.5.

Let $G=(V,E)$ be an undirected graph and, for any $e\in E$ let
$G^{\prime}=(V,E\setminus\\{e\\})$. For all $\gamma\in\mathds{R}_{\geq 0}$ and
$\beta\in[0,1]$ it holds that

$0\leq
Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq\gamma^{2}Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$

and especially

$\mathopen{}\mathclose{{}\left|Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)}\right|\leq\gamma^{2}\min\\{Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right),Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\\}.$

###### Proof.

Without loss of generality, assume $V=[n]$ for some $n\in\mathds{N}_{\geq 2}$
and let $e=\\{i,j\\}$ for $i,j\in[n]$. Note that
$\Sigma_{G}=\Sigma_{G^{\prime}}$, as their vertex sets are identical. Further,
observe that, for all $\sigma\in\Sigma_{G}$, it holds that
$m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)\geq
m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)$. Thus, we
have
$\beta^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\leq\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}$
and $Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq
Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$, which
proves

$0\leq
Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right).$

We proceed by rewriting the partition function of $G^{\prime}$ as

$Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)=\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=0\text{ or
}\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}+\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=1\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}.$

Observe that

$\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=0\text{ or
}\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}=\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=0\text{ or
}\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\leq
Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right).$

For every $k\in[n]$, let
$N_{G^{\prime}}\mathopen{}\mathclose{{}\left(k}\right)$ denote the neighbors
of vertex $k$ in $G^{\prime}$. We have

$\displaystyle\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=1\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}$
$\displaystyle=\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}+2}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}\beta^{\sum_{k\in
N_{G^{\prime}}\mathopen{}\mathclose{{}\left(i}\right)}\sigma\mathopen{}\mathclose{{}\left(k}\right)}\beta^{\sum_{k\in
N_{G^{\prime}}\mathopen{}\mathclose{{}\left(j}\right)}\sigma\mathopen{}\mathclose{{}\left(k}\right)}$
$\displaystyle\leq\gamma^{2}\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G^{\prime}}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G^{\prime}}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}$
$\displaystyle=\gamma^{2}\sum_{\begin{subarray}{c}\sigma\in\Sigma_{G}:\\\
\sigma\mathopen{}\mathclose{{}\left(i}\right)=\sigma\mathopen{}\mathclose{{}\left(j}\right)=0\end{subarray}}\gamma^{\mathopen{}\mathclose{{}\left\lvert\sigma}\right\rvert_{1}}\beta^{m_{G}^{(1)}\mathopen{}\mathclose{{}\left(\sigma}\right)}$
$\displaystyle\leq\gamma^{2}Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right).$

We conclude that
$Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq\mathopen{}\mathclose{{}\left(1+\gamma^{2}}\right)Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$
and thus

$Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq\gamma^{2}Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right).$

The upper bound on
$\mathopen{}\mathclose{{}\left|Z_{G^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)}\right|$
follows immediately. ∎

######  Lemma 3.6.

Let $G=(V,E)$ be an undirected graph and without loss of generality assume
$V=[n]$ for $n\in\mathds{N}$. Let
$E_{H},E_{H^{\prime}}\subseteq\\{\\{n+1,i\\}\mid i\in[n]\\}$, and set
$H=([n+1],E\cup E_{H})$ and $H^{\prime}=([n+1],E\cup E_{H^{\prime}})$. For all
$\gamma\in\mathds{R}_{\geq 0}$ and $\beta\in[0,1]$ it holds that

$\mathopen{}\mathclose{{}\left|Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{H^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)}\right|\leq\gamma
Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq\gamma\min\\{Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right),Z_{H^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\\}.$

###### Proof.

By Lemma 3.5, we know that removing an edge from a graph doesn’t decrease the
partition function. Thus,
$Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$ is maximized by
choosing $E_{H}=\emptyset$ and minimized by choosing $E_{H}=\\{\\{n+1,i\\}\mid
i\in[n]\\}$. Consequently, we have

$Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq(1+\gamma)Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$

and

$Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\geq
Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)+\gamma\geq
Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right).$

As the same holds for $H^{\prime}$, we obtain

$\mathopen{}\mathclose{{}\left|Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)-Z_{H^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)}\right|\leq\gamma
Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)$

and the claim follows by noting that
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\leq\min\\{Z_{H}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right),Z_{H^{\prime}}\mathopen{}\mathclose{{}\left(\gamma,\beta}\right)\\}$.
∎

Based on Lemmas 3.6 and 3.5, we use Corollary 3.3 to prove the following
statement.

######  Theorem 3.7.

Let $W$ be a graphon on the probability space
$\mathcal{X}=(X,\mathcal{A},\xi)$. Let $\gamma:\mathds{N}_{\geq
1}\to\mathds{R}_{\geq 0}$ such that
$\gamma\mathopen{}\mathclose{{}\left(n}\right)\leq\gamma_{0}n^{-\frac{1+\alpha}{2}}$
for some $\gamma_{0}\in\mathds{R}_{\geq 0}$ and $\alpha\in\mathds{R}_{>0}$.
For all $\beta\in[0,1]$, $\varepsilon\in\mathds{R}_{>0}$,
$n>\gamma_{0}^{\frac{2}{\alpha}}$ and $G\sim\mathds{G}_{W,n}$ it holds that

$\mathrm{Pr}\big{[}{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)-\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\right|\geq\varepsilon\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\big{]}\leq\frac{\gamma_{0}^{2}}{\mathopen{}\mathclose{{}\left(n^{\alpha}-\gamma_{0}^{2}}\right)\varepsilon^{2}}.$

###### Proof.

We aim for applying Corollary 3.3 to prove our claim. To this end, for each
$n\in\mathds{N}_{\geq 1}$ we need to write the partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)$
for $G\sim\mathds{G}_{W,n}$ as a function on a product of $\sigma$-finite
probability spaces. At first, an obvious choice seems to be $\mathcal{X}^{n}$
together with $\binom{n}{2}$ additional binary random variables, one for each
potential edge $\\{i,j\\}\in\binom{[n]}{2}$. However, note that the edges
might not necessarily be independent, meaning that the resulting product
distribution would not resemble $\mathds{G}_{W,n}$. Instead, let
$\mathcal{Y}=([0,1],\mathcal{B}\mathopen{}\mathclose{{}\left([0,1]}\right),u)$,
where $\mathcal{B}\mathopen{}\mathclose{{}\left([0,1]}\right)$ is the Borel
algebra restricted to $[0,1]$ and $u$ is the uniform distribution on that
interval. We consider the probability space
$\mathcal{X}^{n}\otimes\mathcal{Y}^{\binom{n}{2}}$.

For $\bm{x}\in X^{n}$ and $\bm{y}\in[0,1]^{\binom{n}{2}}$ let
$\bm{x}\circ\bm{y}\in X^{n}\times[0,1]^{\binom{n}{2}}$ denote the
concatenation of $\bm{x}$ and $\bm{y}$. We construct a measurable function
$g:X^{n}\times[0,1]^{\binom{n}{2}}\to\mathcal{G}_{n}$ by mapping every
$\bm{z}=\bm{x}\circ\bm{y}\in X^{n}\times[0,1]^{\binom{n}{2}}$ with
$\bm{x}=(x_{i})_{i\in[n]}\in X^{n}$ and $\bm{y}=(y_{i,j})_{1\leq i<j\leq
n}\in[0,1]^{\binom{n}{2}}$ to $g(\bm{z})=([n],E)$ such that, for all $i<j$, it
holds that $\\{i,j\\}\in E$ if and only if
$W\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)\geq y_{i,j}$. Simple
calculations show that, for $\bm{z}\sim\xi^{n}\times u^{\binom{n}{2}}$, it
holds that $g(z)\sim\mathds{G}_{W,n}$. Now, let
$f:X^{n}\times[0,1]^{\binom{n}{2}}\to\mathds{R}$ with $\bm{z}\mapsto
Z_{g(z)}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)$.
In order to apply Corollary 3.3, we need to bound the relative change of
$f(\bm{z})$ if we change one component of $\bm{z}$. Let
$\bm{x^{\prime}}=(x_{1},\cdots,x_{i-1},x_{i}^{\prime},x_{i+1},\dots,x_{n})\in
X^{n}$ for any $i\in[n]$. Then $g(\bm{x^{\prime}}\circ\bm{y})$ can only differ
from $g(\bm{z})$ on edges that are incident to vertex $i$. Thus, by Lemma 3.6,
it holds that

$\mathopen{}\mathclose{{}\left|f(\bm{z})-f(\bm{x^{\prime}}\circ\bm{y})}\right|\leq\gamma\mathopen{}\mathclose{{}\left(n}\right)\min\\{f(\bm{z}),f(\bm{x^{\prime}}\circ\bm{y})\\}.$

Now, let $\bm{y^{\prime}}=(y_{i,j}^{\prime})_{1\leq i<j\leq
n}\in[0,1]^{\binom{n}{2}}$ such that $y_{i,j}^{\prime}=y_{i,j}$ except for one
pair $1\leq i<j\leq n$. Note that $g(\bm{z})$ and
$g(\bm{x}\circ\bm{y^{\prime}})$ differ by at most one edge. By Lemma 3.5, we
have

$\mathopen{}\mathclose{{}\left|f(\bm{z})-f(\bm{x}\circ\bm{y^{\prime}})}\right|\leq\gamma\mathopen{}\mathclose{{}\left(n}\right)^{2}\min\\{f(\bm{z}),f(\bm{x}\circ\bm{y^{\prime}})\\}.$

Furthermore, note that for
$\gamma\mathopen{}\mathclose{{}\left(n}\right)\leq\gamma_{0}n^{-\frac{1+\alpha}{2}}$
and $n>\gamma_{0}^{\frac{2}{\alpha}}$ it holds that

$C=n\gamma\mathopen{}\mathclose{{}\left(n}\right)^{2}+\binom{n}{2}\gamma\mathopen{}\mathclose{{}\left(n}\right)^{4}\leq\gamma_{0}^{2}n^{-\alpha}+\gamma_{0}^{4}n^{-2\alpha}\leq
2\gamma_{0}^{2}n^{-\alpha}<2.$

Thus, by Corollary 3.3 we obtain

$\displaystyle\mathrm{Pr}\big{[}{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)-\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\right|\geq\varepsilon\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\big{]}$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(\frac{2}{2-C}-1}\right)\frac{1}{\varepsilon^{2}}$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(\frac{1}{1-\gamma_{0}^{2}n^{-\alpha}}-1}\right)\frac{1}{\varepsilon^{2}}$
$\displaystyle=\frac{\gamma_{0}^{2}}{\mathopen{}\mathclose{{}\left(n^{\alpha}-\gamma_{0}^{2}}\right)\varepsilon^{2}},$

which concludes the proof. ∎

Theorem 1.4 follows immediately from Theorem 3.7.

See 1.4

###### Proof.

For $\varepsilon\leq 1$ and $\delta\leq 1$ it holds that
$n\geq\mathopen{}\mathclose{{}\left(2\gamma_{0}^{2}\varepsilon^{-2}\delta^{-1}}\right)^{\frac{1}{\alpha}}>\gamma_{0}^{\frac{2}{\alpha}}$.
Applying Theorem 3.7 yields

$\displaystyle\mathrm{Pr}\big{[}{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)-\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\right|\geq\varepsilon\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right),\beta}\right)}}\right]}\big{]}$
$\displaystyle\leq\frac{1}{(2\varepsilon^{-2}\delta^{-1}-1)\varepsilon^{2}}$
$\displaystyle=\frac{\varepsilon^{2}\delta}{(2-\varepsilon^{2}\delta)\varepsilon^{2}}$
$\displaystyle=\frac{\delta}{2-\varepsilon^{2}\delta}$
$\displaystyle\leq\delta.\qed$

##  4 Application to repulsive Gibbs point processes

We use our concentration results for antiferromagnetic spin systems to relate
repulsive Gibbs point processes to a hard-core model on carefully constructed
classes of random graphs. To this end, let $(\mathds{X},d)$ be a complete,
separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. For every bounded and measurable
$\mathds{V}\subseteq\mathds{X}$ we define a probability space
$\mathcal{X}_{\mathds{V}}=(\mathds{V},\mathcal{B}_{\mathds{V}},u_{\mathds{V}})$,
where $\mathcal{B}_{\mathds{V}}$ denotes the restriction of $\mathcal{B}$ to
$\mathds{V}$ and $u_{\mathds{V}}$ is the probability measure on
$(\mathds{V},\mathcal{B}_{\mathds{V}})$ that is defined via the constant
density $\frac{1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$ with
respect to $\nu$ restricted to $\mathds{V}$. For every symmetric, repulsive
and measurable pair potential function $\phi:\mathds{X}^{2}\to\mathds{R}_{\geq
0}\cup\\{\infty\\}$ and all $n\in\mathds{N}_{\geq 1}$. Define
$W_{\phi}:\mathds{V}^{2}\to[0,1]$ with
$W_{\phi}\mathopen{}\mathclose{{}\left(x,y}\right)=1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x,y}\right)}$
and observe that $W_{\phi}$ is a graphon on $\mathcal{X}_{\mathds{V}}$. We
proceed by considering the random graph model
$\zeta^{(n)}_{\mathds{V},\phi}=\mathds{G}_{W_{\phi},n}$.

The following lemma relates the expected hard-core partition function on
$\zeta^{(n)}_{\mathds{V},\phi}$ with the partition function of the continuous
Gibbs point process
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$.

######  Lemma 4.1.

Let $(\mathds{X},d)$ be a complete separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$ and let
$\phi:\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a symmetric
repulsive potential. For all $\varepsilon\in\mathds{R}_{>0}$ and $n\geq
2\varepsilon^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(2\varepsilon^{-1}}\right)^{2}}\right\\}$
it holds that

$\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\leq\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\leq\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right).$

###### Proof.

We start by rewriting the hard-core partition function as

$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)=1+\sum_{k=1}^{n}\lambda^{k}\frac{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}{n^{k}}\sum_{S\in\binom{[n]}{k}}\prod_{\\{i,j\\}\in\binom{S}{2}}\mathds{1}_{\\{i,j\\}\notin
E}.$

Thus, by linearity of expectation we have

$\displaystyle\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]$
$\displaystyle=1+\sum_{k=1}^{n}\lambda^{k}\frac{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}{n^{k}}\sum_{S\in\binom{[n]}{k}}\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{\prod_{\\{i,j\\}\in\binom{S}{2}}\mathds{1}_{\\{i,j\\}\notin
E}}}\right]$
$\displaystyle=1+\sum_{k=1}^{n}\lambda^{k}\frac{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}{n^{k}}\sum_{S\in\binom{[n]}{k}}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\bigwedge_{\\{i,j\\}\in\binom{S}{2}}\\{i,j\\}\notin
E}}\right].$

Next, observe that for all $S\in\binom{[n]}{k}$ with
$\mathopen{}\mathclose{{}\left|S}\right|=k$

$\displaystyle\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\bigwedge_{\\{i,j\\}\in\binom{S}{2}}\\{i,j\\}\notin
E}}\right]$
$\displaystyle=\int_{\mathds{V}^{n}}\prod_{\\{i,j\\}\in\binom{S}{2}}\mathopen{}\mathclose{{}\left(1-W_{\phi}\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\right)u^{n}_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=\int_{\mathds{V}^{n}}\prod_{\\{i,j\\}\in\binom{S}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}u^{n}_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=\frac{1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{n}}\int_{\mathds{V}^{n}}\prod_{\\{i,j\\}\in\binom{S}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{n}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=\frac{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{n-k}}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{n}}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=\frac{1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right).$

This yields

$\displaystyle\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]$
$\displaystyle=1+\sum_{k=1}^{n}\lambda^{k}\frac{1}{n^{k}}\sum_{S\in\binom{[n]}{k}}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=1+\sum_{k=1}^{n}\lambda^{k}\frac{\binom{n}{k}}{n^{k}}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle=1+\sum_{k=1}^{n}\frac{\lambda^{k}}{k!}\prod_{i=0}^{k-1}\mathopen{}\mathclose{{}\left(1-\frac{i}{n}}\right)\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right),$

from which the upper bound

$\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\leq\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$

follows immediately.

For the lower bound set

$S_{m}=1+\sum_{k=1}^{m}\frac{\lambda^{k}}{k!}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$

for any $1\leq m\leq n$. Observe that

$\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\geq\mathopen{}\mathclose{{}\left(1-\frac{m}{n}}\right)^{m}S_{m}.$

Thus, for $n\geq 2\varepsilon^{-1}m^{2}$ Bernoulli’s inequality yields

$\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\geq\mathopen{}\mathclose{{}\left(1-\frac{m^{2}}{n}}\right)S_{m}\geq\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)S_{m}.$

Furthermore, note that

$\displaystyle\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)-S_{m}$
$\displaystyle=\sum_{k=m+1}^{\infty}\frac{\lambda^{k}}{k!}\int_{\mathds{V}^{k}}\prod_{\\{i,j\\}\in\binom{[k]}{2}}\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{i},x_{j}}\right)}\nu^{k}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle\leq\sum_{k=m+1}^{\infty}\frac{\lambda^{k}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{k}}{k!},$

where the last inequality comes from the fact that $\phi$ is non-negative.
Next, observe that this is equal to the error of the Taylor expansion of
$\mathrm{e}^{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$
around $0$, truncated after $m$ terms. Thus, by Lagrange’s remainder formula,
we obtain

$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)-S_{m}\leq\frac{\mathrm{e}^{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}{(m+1)!}\mathopen{}\mathclose{{}\left(\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\right)^{m+1}.$

Choosing
$m\geq\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{3}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right),\ln\mathopen{}\mathclose{{}\left(2\varepsilon^{-1}}\right)}\right\\}$
and using the fact that
$(m+1)!>\mathopen{}\mathclose{{}\left(\frac{m+1}{\mathrm{e}missing}}\right)^{m+1}$
yields

$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)-S_{m}\leq\mathopen{}\mathclose{{}\left(\frac{\mathrm{e}^{2}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{m+1}}\right)^{m+1}\leq\mathrm{e}^{-(m+1)}\leq\frac{\varepsilon}{2}.$

As $\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\geq 1$,
we get

$S_{m}\geq\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)-\frac{\varepsilon}{2}\geq\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right).$

For $n\geq
2\varepsilon^{-1}m^{2}=2\varepsilon^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(2\varepsilon^{-1}}\right)^{2}}\right\\}$
we obtain

$\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\geq\mathopen{}\mathclose{{}\left(1-\frac{m}{n}}\right)^{m}S_{m}\geq\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)^{2}\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\geq\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right),$

which proves the claim. ∎

See 1.1

###### Proof.

By setting $\alpha=1$ and
$\gamma_{0}=\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$ and
using the fact that

$n\geq
4\varepsilon^{-2}\delta^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(4\varepsilon^{-1}}\right)^{2}}\right\\}\geq\mathopen{}\mathclose{{}\left(2\gamma_{0}^{2}\mathopen{}\mathclose{{}\left(\frac{\varepsilon}{2}}\right)^{-2}\delta^{-1}}\right)^{\frac{1}{\alpha}}$

Theorem 1.4 yields

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)-\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]}\right|\geq\frac{\varepsilon}{2}\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]}}\right]\leq\delta.$

Furthermore, by Lemma 4.1 we know that for

$n\geq
4\varepsilon^{-2}\delta^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(4\varepsilon^{-1}}\right)^{2}}\right\\}\geq
2\mathopen{}\mathclose{{}\left(\frac{\varepsilon}{2}}\right)^{-1}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(2\mathopen{}\mathclose{{}\left(\frac{\varepsilon}{2}}\right)^{-1}}\right)^{2}}\right\\}$

it holds that

$\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\leq\mathrm{E}_{G\sim\zeta^{(n)}_{\mathds{V},\phi}}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\leq\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right).$

Thus, we have

$\mathopen{}\mathclose{{}\left(1+\frac{\varepsilon}{2}}\right)\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\leq\mathopen{}\mathclose{{}\left(1+\frac{\varepsilon}{2}}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\leq\mathopen{}\mathclose{{}\left(1+\varepsilon}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$

and similarly

$\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)\mathrm{E}\mathopen{}\mathclose{{}\left[{Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)}}\right]\geq\mathopen{}\mathclose{{}\left(1-\frac{\varepsilon}{2}}\right)^{2}\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\geq\mathopen{}\mathclose{{}\left(1-\varepsilon}\right)\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right).$

We obtain

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)-\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}\right|\geq\varepsilon\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}}\right]\leq\delta,$

which proves the claim. ∎

###  4.1 Approximating the partition function

One of the main applications of Theorem 1.1 is that it yields a rather simple
randomized procedure for approximating
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$. The
rough idea is as follows:

  1. 1.

For $n\in\mathds{N}$ sufficiently large, sample a graph $G$ from
$\zeta^{(n)}_{\mathds{V},\phi}$.

  2. 2.

Approximate
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
and use the result as an approximation for
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$.

We are especially interested in obtaining an algorithm that is asymptotically
efficient in the volume $\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$,
as this gives a natural way to parameterize the algorithmic problem. More
specifically, we want to characterize the regime of the fugacity $\lambda$ in
terms of the potential $\phi$ for which we can get a randomized
$\varepsilon$-approximation of
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ in time
polynomial in $\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$ and
$\frac{1}{\varepsilon}$. We characterize this fugacity regime in terms of the
temperedness constant

$C_{\phi}=\operatorname*{ess\,sup}_{x_{1}\in\mathds{X}}\int_{\mathds{X}}\mathopen{}\mathclose{{}\left|1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)}}\right|\nu\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right),$

where $\operatorname*{ess\,sup}$ denotes the essential supremum (i.e., an
upper bound that holds almost everywhere).

In order to ensure that the approximation algorithm runs efficiently in
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$, two ingredients are
important. First, we need to bound how large $n$ needs to be chosen to ensure
that
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
is close to
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ with high
probability. Second, we need to ensure that
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
can be approximated in time polynomial in
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$. Obviously, both
requirements are satisfied if
$n\in\mathrm{poly}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}\right)$
is sufficient and if
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
can be approximated in time
$\mathrm{poly}\mathopen{}\mathclose{{}\left({n}}\right)$. To tackle the first
part, Theorem 1.1 gives a useful tool. For the second part, we will use some
well known results on approximating the hard-core partition function.

######  Theorem 4.2 ([44, Corollary $8.4$] and [3, Theorem $1$]).

Let $G=(V,E)$ be an undirected graph with maximum vertex degree bounded by
$d_{G}\in\mathds{N}_{\geq 2}$ and let $\gamma\in\mathds{R}_{\geq 0}$ with

$\gamma<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right)=\frac{\mathopen{}\mathclose{{}\left(d_{G}-1}\right)^{d_{G}-1}}{\mathopen{}\mathclose{{}\left(d_{G}-2}\right)^{d_{G}}}.$

Then, for all $\varepsilon\in(0,1]$, there is a randomized
$\varepsilon$-approximation algorithm for the hard-core partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma}\right)$ with running time
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\mathopen{}\mathclose{{}\left|V}\right|^{2}\varepsilon^{-2}}}\right)$.

######  Remark 4.3.

In [44] the result above is only stated for $\gamma<\frac{2}{d_{G}missing}$ as
an older mixing time result for Glauber dynamics from [46] is used. Combining
their approach with the more recent mixing time bound in [3] gives the desired
bound of
$\gamma<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right)$.

Thus, arguing that $Z_{G}$ for $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ can be
approximated in time $\mathrm{poly}\mathopen{}\mathclose{{}\left({n}}\right)$
boils down to obtaining a probabilistic upper bound on $d_{G}$. We use the
following simple lemma.

######  Lemma 4.4.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$ and let
$\phi:\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a symmetric
repulsive potential. Assume $C_{\phi}>0$. For $\alpha\in\mathds{R}_{>0}$,
$q\in(0,1]$, $n\geq
3\max\mathopen{}\mathclose{{}\left\\{\alpha^{-1},\alpha^{-2}}\right\\}\ln\mathopen{}\mathclose{{}\left(q^{-1}}\right)C_{\phi}^{-1}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)+1$
and $G\sim\zeta^{(n)}_{\mathds{V},\phi}$ it holds that

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\geq(1+\alpha)\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}}}\right]\leq
qn.$

###### Proof.

By union bound, it is sufficient to argue that, for each $i\in[n]$ it holds
that

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(i}\right)\geq(1+\alpha)\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}}}\right]\leq
q,$

where $d_{G}\mathopen{}\mathclose{{}\left(i}\right)$ denotes the degree of
vertex $i\in[n]$ in $G$. Now, observe that the random variables
$d_{G}\mathopen{}\mathclose{{}\left(i}\right)$ for $i\in[n]$ are identically
distributed. Thus, we can focus on
$d_{G}\mathopen{}\mathclose{{}\left(n}\right)$ for ease of notation. By
definition, it holds for $k\in[n-1]\cup\\{0\\}$ that

$\displaystyle\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)=k}}\right]$
$\displaystyle\hskip
30.00005pt=\sum_{S\in\binom{[n-1]}{k}}\bigintsss_{\mathds{V}^{n}}\mathopen{}\mathclose{{}\left(\prod_{i\in
S}W_{\phi}\mathopen{}\mathclose{{}\left(x_{n},x_{i}}\right)}\right)\cdot\mathopen{}\mathclose{{}\left(\prod_{i\in[n-1]\setminus
S}(1-W_{\phi}\mathopen{}\mathclose{{}\left(x_{n},x_{i}}\right))}\right)u^{n}_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}\bm{x}}\right)$
$\displaystyle\hskip
30.00005pt=\bigintsss_{\mathds{V}}\sum_{S\in\binom{[n-1]}{k}}\mathopen{}\mathclose{{}\left(\prod_{i\in
S}\int_{\mathds{V}}W_{\phi}\mathopen{}\mathclose{{}\left(x_{n},x_{i}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{i}}\right)}\right)\cdot\mathopen{}\mathclose{{}\left(\prod_{i\in[n-1]\setminus
S}\int_{\mathds{V}}1-W_{\phi}\mathopen{}\mathclose{{}\left(x_{n},x_{i}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{i}}\right)}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{n}}\right)$
$\displaystyle\hskip
30.00005pt=\int_{\mathds{V}}\binom{n-1}{k}\mathopen{}\mathclose{{}\left(\int_{\mathds{V}}W_{\phi}\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right)}\right)^{k}\mathopen{}\mathclose{{}\left(1-\int_{\mathds{V}}W_{\phi}\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right)}\right)^{n-1-k}\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right).$

For every $x_{1}\in\mathds{V}$, let $B_{x_{1}}$ be a binomial random variable
with $n-1$ trials and with success probability
$\int_{\mathds{V}}W_{\phi}\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right)$.
We obtain

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)=k}}\right]=\int_{\mathds{V}}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B_{x_{1}}=k}}\right]\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right),$

which implies for all $a\in[0,n-1]$

$\displaystyle\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)\geq
a}}\right]$ $\displaystyle=\sum_{k=\lceil
a\rceil}^{n-1}\int_{\mathds{V}}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B_{x_{1}}=k}}\right]\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right)$
$\displaystyle=\int_{\mathds{V}}\sum_{k=\lceil
a\rceil}^{n-1}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B_{x_{1}}=k}}\right]\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right)$
$\displaystyle=\int_{\mathds{V}}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B_{x_{1}}\geq
a}}\right]\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right).$

Next, let $B$ be a binomial random variable with $n-1$ trials and success
probability
$\frac{C_{\phi}missing}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$.
Observe that, by the definition of $C_{\phi}$, it holds for $\nu$-almost all
$x_{1}\in\mathds{V}$ that
$\int_{\mathds{V}}W_{\phi}\mathopen{}\mathclose{{}\left(x_{1},x_{2}}\right)\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{2}}\right)\leq\frac{C_{\phi}missing}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$.
Thus, we have that $B$ stochastically dominates $B_{x_{1}}$ for
$u_{\mathds{V}}$-almost all $x_{1}\in\mathds{V}$. Consequently, we obtain

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)\geq
a}}\right]\leq\int_{\mathds{V}}\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B\geq
a}}\right]\,u_{\mathds{V}}\mathopen{}\mathclose{{}\left(\text{d}x_{1}}\right)=\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B\geq
a}}\right].$

Observing that
$\mathrm{E}\mathopen{}\mathclose{{}\left[{B}}\right]=\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}$
and applying Chernoff bound yields

$\displaystyle\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)\geq(1+\alpha)\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}}}\right]\leq\mathrm{e}^{-\frac{\min\mathopen{}\mathclose{{}\left\\{\alpha,\alpha^{2}}\right\\}C_{\phi}(n-1)}{3\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}.$

Setting $n\geq
3\max\mathopen{}\mathclose{{}\left\\{\alpha^{-1},\alpha^{-2}}\right\\}\ln\mathopen{}\mathclose{{}\left(q^{-1}}\right)C_{\phi}^{-1}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)+1$
we have
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\mathopen{}\mathclose{{}\left(n}\right)\geq(1+\alpha)\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}}}\right]\leq
q$, which proves the claim. ∎

Combining Theorem 1.1, Lemma 4.4, and Theorem 4.2, we obtain the following
algorithmic result.

See 1.2

###### Proof.

We start by giving a more precise outline of the algorithmic idea. To this
end, we define

$N=\max\mathopen{}\mathclose{{}\left\\{\begin{subarray}{c}324\varepsilon^{-2}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\,\ln\mathopen{}\mathclose{{}\left(4\varepsilon^{-1}}\right)^{2}}\right\\},\\\
24\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\ln\mathopen{}\mathclose{{}\left(24\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\right)^{2}\end{subarray}}\right\\}.$

We now use the following procedure to approximate
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$:

  1. 1.

Choose some integer $n\geq N$.

  2. 2.

Draw a graph $G$ from $\zeta^{(n)}_{\mathds{V},\phi}$.

  3. 3.

If
$d_{G}\geq\frac{\mathrm{e}n}{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$,
return an arbitrary value.

  4. 4.

Else, use the algorithm from Theorem 4.2 to
$\frac{\varepsilon}{3}$-approximate
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
with an error probability of at most $\frac{1}{9}$ and return the result.

We proceed by arguing that this procedure yields an
$\varepsilon$-approximation of
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ in time
$\mathrm{poly}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\varepsilon^{-1}}}\right)$.
We start by bounding the probability that the computed value is not an
$\varepsilon$-approximation.

First, we assume that, whenever
$d_{G}\geq\frac{\mathrm{e}n}{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$,
the algorithm returns no $\varepsilon$-approximation in step 3. Let $A$ be the
event that this happens. Second, let $B$ denote the event that the hard-core
partition function
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
the graph $G$ that we drew in step 2 is not an
$\frac{\varepsilon}{3}$-approximation of
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$. Finally,
let $C$ denote the event we do not manage to compute an
$\frac{\varepsilon}{3}$-approximation of
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
in step 4. Note that the probability that the above procedure does not output
an $\varepsilon$-approximation for
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$ is upper
bounded by

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{A\cup(B\cap\overline{A})\cup(C\cap\overline{B}\cap\overline{A})}}\right]\leq\mathrm{Pr}\mathopen{}\mathclose{{}\left[{A}}\right]+\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B}}\right]+\mathrm{Pr}\mathopen{}\mathclose{{}\left[{C}}\right].$

We proceed with bounding each of these probabilities separately.

To bound $\mathrm{Pr}\mathopen{}\mathclose{{}\left[{A}}\right]$, let
$z=24\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$.
As we are interested in asymptotic behavior in terms of
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$, we may assume that
$\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$ is sufficiently large to
ensure $z\geq 5$. Note that for this, we have to exclude the case $\lambda=0$,
which trivially yields
$\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)=1$. Now,
observe that for $z\geq 5$ it holds that $z\ln(z)^{2}\geq
z\ln\mathopen{}\mathclose{{}\left(z\ln(z)^{2}}\right)$. Next, observe that
$n\geq z\ln(z)^{2}$. Thus, we have $n\geq z\ln(n)$. Furthermore, by $n\geq
5\ln(5)^{2}\geq\mathrm{e}\geq 2$, we have

$\displaystyle n-1$ $\displaystyle\geq\frac{n}{2}$ $\displaystyle\geq
12\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\ln(n)$
$\displaystyle\geq
3\mathopen{}\mathclose{{}\left(\ln\mathopen{}\mathclose{{}\left(9}\right)+1}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\ln(n)$
$\displaystyle=3\mathopen{}\mathclose{{}\left(\ln\mathopen{}\mathclose{{}\left(9}\right)\ln(n)+\ln(n)}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)$
$\displaystyle\geq
3\ln\mathopen{}\mathclose{{}\left(9n}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right).$

Thus, we obtain

$n\geq 3\max\mathopen{}\mathclose{{}\left\\{\frac{\lambda
C_{\phi}missing}{\mathrm{e}-\lambda
C_{\phi}missing},\mathopen{}\mathclose{{}\left(\frac{\lambda
C_{\phi}missing}{\mathrm{e}-\lambda
C_{\phi}missing}}\right)^{2}}\right\\}\ln\mathopen{}\mathclose{{}\left(9n}\right)C_{\phi}^{-1}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)+1$

and by Lemma 4.4

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\geq\frac{\mathrm{e}n}{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}}}\right]\leq\mathrm{Pr}\mathopen{}\mathclose{{}\left[{d_{G}\geq\mathopen{}\mathclose{{}\left(1+\frac{\mathrm{e}-\lambda
C_{\phi}missing}{\lambda
C_{\phi}missing}}\right)\frac{n-1}{\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}C_{\phi}}}\right]\leq\frac{1}{9}.$

To bound $\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B}}\right]$, note that for
$n\geq
324\varepsilon^{-2}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\,\ln\mathopen{}\mathclose{{}\left(4\varepsilon^{-1}}\right)^{2}}\right\\}$
Theorem 1.1 yields

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{B}}\right]=\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\mathopen{}\mathclose{{}\left|Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)-\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}\right|\geq\frac{\varepsilon}{3}\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}}\right]\leq\frac{1}{9}.$

Finally, note that, by Theorem 4.2, we can obtain an
$\frac{\varepsilon}{3}$-approximation of
$Z_{G}\mathopen{}\mathclose{{}\left(\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}}\right)$
with error probability at most
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{C}}\right]\leq\frac{1}{9}$ in time
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({n^{2}\varepsilon^{-2}}}\right)$
as long as
$\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right)$.
As we only run the approximation for graphs $G$ with
$d_{G}<\frac{\mathrm{e}n}{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$
it holds that

$\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}<\frac{\mathrm{e}missing}{d_{G}missing}<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right),$

proving that the requirement is satisfied.

We obtain that the error probability is bounded by $\frac{1}{3}$. To finish
the proof, we need to argue that our algorithm has the desired running time.
To this end, note that
$N\in\mathrm{O}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-2}}}\right)$.
Thus, we can also choose
$n\in\mathrm{O}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-2}}}\right)$.
By assumption, step 2 can be computed in time
$t_{\mathds{V},\phi}\mathopen{}\mathclose{{}\left(n}\right)=t_{\mathds{V},\phi}\mathopen{}\mathclose{{}\left(\mathrm{O}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-2}}}\right)}\right)$.
Furthermore, step 3 can be computed in time
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({n^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{-1}}}\right)=\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{3}\varepsilon^{-4}}}\right)$
and, by Theorem 4.2, step 4 runs in time
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({n^{2}\varepsilon^{-2}}}\right)=\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{4}\varepsilon^{-6}}}\right)$
for
$\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}<\gamma_{\text{c}}\mathopen{}\mathclose{{}\left(d_{G}}\right)$.
Consequently, the overall running time is in
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{4}\varepsilon^{-6}}}\right)+t_{\mathds{V},\phi}\mathopen{}\mathclose{{}\left(\mathrm{O}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-2}}}\right)}\right)$.
∎

##  5 Sampling from repulsive Gibbs point processes

In this section, we propose an approximate sampling algorithm for the Gibbs
measure of a repulsive Gibbs point process, based in random hard-core models.
More precisely, we investigate the sampling procedure given by Algorithm 1

Data: Instance of a repulsive Gibbs point process $(\mathds{V},\lambda,\phi)$,
error bound $\varepsilon\in(0,1]$

Result: multiset of points in $\mathds{V}$

1 set
$n=\mathopen{}\mathclose{{}\left\lceil\max\mathopen{}\mathclose{{}\left\\{\begin{subarray}{c}8\frac{18^{2}\cdot
12}{\varepsilon^{3}}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(\frac{4\cdot
18}{\varepsilon}}\right)}\right\\},\\\
6\ln\mathopen{}\mathclose{{}\left(\frac{4\mathrm{e}missing}{\varepsilon}}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\ln\mathopen{}\mathclose{{}\left(3\ln\mathopen{}\mathclose{{}\left(\frac{4\mathrm{e}missing}{\varepsilon}}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\right)^{2}\end{subarray}}\right\\}}\right\rceil$;

2 for each $i\in[n]$ draw $X_{i}\sim u_{\mathds{V}}$ independently;

3 draw $E\subseteq\binom{[n]}{2}$ s.t. $\\{i,j\\}\in E$ with probability
$W_{\phi}\mathopen{}\mathclose{{}\left(X_{i},X_{j}}\right)=1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(X_{i},X_{j}}\right)}$
independently;

4 set $G=([n],E)$;

5 if  _maximum degree
$d_{G}\geq\frac{\mathrm{e}n}{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}$_
then

6 set $X=\emptyset$;

7

8else

9 sample $\sigma\in\Sigma_{G}$ $\frac{\varepsilon}{4}$-approximately from the
hard-core distribution
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}$
where
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}$;

10 set $X=\\{X_{i}\mid i\in[n]\text{ s.t.
}\sigma\mathopen{}\mathclose{{}\left(i}\right)=1\\}$ (possibly multiset);

11

12 end if

13return $X$;

Algorithm 1 Approximate sampling algorithm for a repulsive point process
$(\mathds{V},\lambda,\phi)$.

Our main theorem in this section is as follows.

######  Theorem 5.1.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$ and let
$\phi:\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a symmetric
repulsive potential. Assume we can sample from the uniform distribution
$u_{\mathds{V}}$ in time $t_{\mathds{V}}$ and, for every $x,y\in\mathds{V}$,
evaluate $\phi\mathopen{}\mathclose{{}\left(x,y}\right)$ in time $t_{\phi}$.
If the Gibbs point process
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
simple and $\lambda<\frac{\mathrm{e}missing}{C_{\phi}missing}$ then, for every
$\varepsilon\in\mathds{R}_{>0}$, Algorithm 1 samples
$\varepsilon$-approximately from
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ and has
running time in
$\widetilde{\mathrm{O}}\mathopen{}\mathclose{{}\left({\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-4}+\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2}\varepsilon^{-3}t_{\mathds{V}}+\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{4}\varepsilon^{-6}t_{\phi}}}\right)$.

Theorem 1.3 follows immediately from the theorem above. To prove Theorem 5.1,
we start by analyzing a simplified algorithm, given in Algorithm 2.

Data: Instance of a repulsive Gibbs point process $(\mathds{V},\lambda,\phi)$,
error bound $\varepsilon\in(0,1]$

Result: multiset of points in $\mathds{V}$

1 set
$n=\mathopen{}\mathclose{{}\left\lceil\max\mathopen{}\mathclose{{}\left\\{\begin{subarray}{c}8\frac{18^{2}\cdot
12}{\varepsilon^{3}}\max\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{6}\lambda^{2}\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)^{2},\ln\mathopen{}\mathclose{{}\left(\frac{4\cdot
18}{\varepsilon}}\right)}\right\\},\\\
6\ln\mathopen{}\mathclose{{}\left(\frac{4\mathrm{e}missing}{\varepsilon}}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\ln\mathopen{}\mathclose{{}\left(3\ln\mathopen{}\mathclose{{}\left(\frac{4\mathrm{e}missing}{\varepsilon}}\right)\max\mathopen{}\mathclose{{}\left\\{\frac{1}{\mathrm{e}-\lambda
C_{\phi}missing},\frac{\lambda
C_{\phi}missing}{\mathopen{}\mathclose{{}\left(\mathrm{e}-\lambda
C_{\phi}}\right)^{2}}}\right\\}\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\right)^{2}\end{subarray}}\right\\}}\right\rceil$;

2 for each $i\in[n]$ draw $X_{i}\sim u_{\mathds{V}}$ independently;

3 draw $E\subseteq\binom{[n]}{2}$ s.t. $\\{i,j\\}\in E$ with probability
$W_{\phi}\mathopen{}\mathclose{{}\left(X_{i},X_{j}}\right)=1-\mathrm{e}^{-\phi\mathopen{}\mathclose{{}\left(X_{i},X_{j}}\right)}$
independently;

4 set $G=([n],E)$;

5 sample $\tau\in\Sigma_{G}$ exactly from the hard-core distribution
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}$
where
$\gamma\mathopen{}\mathclose{{}\left(n}\right)=\frac{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}{n}$;

6 set $Y=\\{X_{i}\mid i\in[n]\text{ s.t.
}\tau\mathopen{}\mathclose{{}\left(i}\right)=1\\}$ (possibly multiset);

7 return $Y$;

Algorithm 2 Modified sampling process

The main difference between Algorithm 1 and Algorithm 2 is that the latter one
does not check if the maximum degree of the sampled graph $G$ is bounded and
that is assumes access to a perfect sampler for
$\mu_{G}^{\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}$.
It is not clear if such a perfect sampler for the hard-core Gibbs distribution
can be realized in polynomial time, especially for arbitrary vertex degrees.
Therefore, Algorithm 2 is not suitable for algorithmic applications. However,
the main purpose of Algorithm 2 is that the distribution of point multisets
that it outputs are much easier to analyze. We use this, together with a
coupling argument, to bound the total variation distance between the output of
Algorithm 1 and
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$. Once
this is done, it remains to show that Algorithm 1 satisfies the running time
requirements, given in Theorem 5.1.

To analyze the output distribution of Algorithm 2, we start by considering the
resulting distribution of multisets of points (or counting measures
respectively) when conditioning on the event that the hard-core partition
function
$Z_{G}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)$
of the drawn graph $G$ is close to the partition function of the continuous
process $\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)$.
More specifically, for any given $n$ and $\alpha\in\mathds{R}_{\geq 0}$, let
$A^{\mathopen{}\mathclose{{}\left(n}\right)}_{\alpha}=\\{H\in\mathcal{G}_{n}\mid\mathopen{}\mathclose{{}\left|Z_{H}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)-\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}\right|\leq\alpha\Xi_{\mathds{V}}\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)\\}$.
We derive an explicit density for the output of Algorithm 2 with respect to a
Poisson point process under the condition that $G\in
A^{\mathopen{}\mathclose{{}\left(n}\right)}_{\alpha}$ for some sufficiently
small $\alpha$. To this end, we use the following characterization of simple
point processes via so called _void probabilities_.

######  Theorem 5.2 (Rényi–Mönch, see [13, Theorem 9.2.XII]).

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the associated Borel algebra. Let $P$ and $Q$ be simple point process on
$(\mathds{X},d)$. If, for $\eta_{P}\sim P$ and $\eta_{Q}\sim Q$ and for all
bounded $B\in\mathcal{B}$, it holds that

$\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\eta_{P}(B)=0}}\right]=\mathrm{Pr}\mathopen{}\mathclose{{}\left[{\eta_{Q}(B)=0}}\right],$

then $P=Q$.

Theorem 5.2 greatly simplifies proving that a given candidate function
actually is a valid density for the point process in question, as it implies
that it is sufficient to check if it yields the correct void probabilities.

Before we proceed, we introduce some additional notation that is useful for
stating and proving our next lemmas. For a given graph $H=(V,E)$, we denote by
$\mathcal{I}\mathopen{}\mathclose{{}\left(H}\right)\subseteq 2^{V}$ the set of
all independent sets in $H$. Moreover, for every spin configuration
$\sigma\in\Sigma_{H}$, we denote by $S_{\sigma}$ the set of all vertices $v\in
V$ with $\sigma\mathopen{}\mathclose{{}\left(v}\right)=1$. Note that, for a
hard-core model on $H$ with $\gamma>0$, this construction gives a one-to-one
correspondence between $\mathcal{I}\mathopen{}\mathclose{{}\left(H}\right)$
and the set of spin configurations $\sigma\in\Sigma_{H}$ with
$\mu_{H}^{\mathopen{}\mathclose{{}\left(\gamma}\right)}\mathopen{}\mathclose{{}\left(\sigma}\right)>0$.
Therefore, it is often convenient to argue about elements in
$\mathcal{I}\mathopen{}\mathclose{{}\left(H}\right)$ instead of using spin
configurations.

######  Lemma 5.3.

Let $(\mathds{X},d)$ be a complete, separable metric space, let
$\mathcal{B}=\mathcal{B}\mathopen{}\mathclose{{}\left(\mathds{X}}\right)$ be
the Borel algebra and let $\nu$ be a locally finite reference measure on
$(\mathds{X},\mathcal{B})$. Let $\mathds{V}\subseteq\mathds{X}$ be bounded and
measurable, let $\lambda\in\mathds{R}_{\geq 0}$ and let
$\phi:\mathds{X}^{2}\to\mathds{R}_{\geq 0}\cup\\{\infty\\}$ be a symmetric
repulsive potential. Furthermore, for any given $\varepsilon\in(0,1]$, let
$\widehat{P_{\varepsilon}}$ be the point process produced by Algorithm 2
conditioned on $G\in
A^{\mathopen{}\mathclose{{}\left(n}\right)}_{\frac{\varepsilon}{12}}$, and let
$Q_{\lambda}$ denote a Poisson point process with intensity $\lambda$. If the
Gibbs point process
$P_{\mathds{V}}^{\mathopen{}\mathclose{{}\left(\lambda,\phi}\right)}$ is
simple, then $\widehat{P_{\varepsilon}}$ has a density with respect to $Q$ of
the form

$\displaystyle
g_{\varepsilon}\mathopen{}\mathclose{{}\left(\eta}\right)=\mathds{1}_{\eta\in\mathcal{N}_{\mathds{V}}}$
$\displaystyle\mathrm{Pr}\mathopen{}\mathclose{{}\left[{G\in
A^{\mathopen{}\mathclose{{}\left(n}\right)}_{\frac{\varepsilon}{12}}}}\right]^{-1}\mathopen{}\mathclose{{}\left(\prod_{i=0}^{\eta\mathopen{}\mathclose{{}\left(\mathds{V}}\right)-1}1-\frac{i}{n}}\right)\mathds{1}_{\eta\mathopen{}\mathclose{{}\left(\mathds{V}}\right)\leq
n}$
$\displaystyle\cdot\mathopen{}\mathclose{{}\left(\prod_{\\{x,y\\}\in\binom{X_{\eta}}{2}}\mathrm{e}^{-N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)N_{y}\mathopen{}\mathclose{{}\left(\eta}\right)\phi\mathopen{}\mathclose{{}\left(x,y}\right)}}\right)\mathopen{}\mathclose{{}\left(\prod_{x\in
X_{\eta}}\mathrm{e}^{-\frac{N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)(N_{x}\mathopen{}\mathclose{{}\left(\eta}\right)-1)}{2}\phi\mathopen{}\mathclose{{}\left(x,x}\right)}}\right)\Psi^{\mathopen{}\mathclose{{}\left(\eta\mathopen{}\mathclose{{}\left(\mathds{V}}\right)}\right)}_{n}\mathopen{}\mathclose{{}\left(\varphi\mathopen{}\mathclose{{}\left(\eta}\right)}\right)\mathrm{e}^{\lambda\nu\mathopen{}\mathclose{{}\left(\mathds{V}}\right)},$

where $\varphi$ maps every finite counting measure $\eta$ to an arbitrary but
fixed tuple
$(x_{1},\dots,x_{\eta\mathopen{}\mathclose{{}\left(\mathds{X}}\right)})$ such
that
$\eta=\sum_{i=1}^{\eta\mathopen{}\mathclose{{}\left(\mathds{X}}\right)}\delta_{x_{i}}$
and

$\displaystyle\Psi^{\mathopen{}\mathclose{{}\left(k}\right)}_{n}\mathopen{}\mathclose{{}\left(\bm{x}}\right)=\sum_{\begin{subarray}{c}H\in
A^{\mathopen{}\mathclose{{}\left(n}\right)}_{\frac{\varepsilon}{12}}:\\\
[k]\in\mathcal{I}\mathopen{}\mathclose{{}\left(H}\right)\end{subarray}}\frac{1}{Z_{H}\mathopen{}\mathclose{{}\left(\gamma\mathopen{}\mathclose{{}\left(n}\right)}\right)}\bigintss_{\mathds{V}^{n-k}}$