Abstract 1 Introduction 2 Proof Outline of Theorems 1 and 2 3 Weak spatial mixing within the ordered phase 4 Fast convergence of the RC dynamics and proof of Theorem 1 References

Low-Temperature Sampling on Sparse Random Graphsthanks: For the Purpose of Open Access, the Authors Have Applied a CC BY Public Copyright Licence to Any Author Accepted Manuscript Version Arising from This Submission. All Data Is Provided in Full in the Results Section of This Paper.

Andreas Galanis ORCID Department of Computer Science, University of Oxford, UK Leslie Ann Goldberg ORCID Department of Computer Science, University of Oxford, UK Paulina Smolarova ORCID Department of Computer Science, University of Oxford, UK
Abstract

We consider sampling in the so-called low-temperature regime, which is typically characterised by non-local behaviour and strong global correlations. Canonical examples include sampling independent sets on bipartite graphs and sampling from the ferromagnetic q-state Potts model. Low-temperature sampling is computationally intractable for general graphs, but recent advances based on the polymer method have made significant progress for graph families that exhibit certain expansion properties that reinforce the correlations, including for example expanders, lattices and dense graphs.

One of the most natural graph classes that has so far escaped this algorithmic framework is the class of sparse Erdős-Rényi random graphs whose expansion only manifests for sufficiently large subsets of vertices; small sets of vertices on the other hand have vanishing expansion which makes them behave independently from the bulk of the graph and therefore weakens the correlations. At a more technical level, the expansion of small sets is crucial for establishing the Kotecky-Priess condition which underpins the applicability of the framework.

Our main contribution is to develop the polymer method in the low-temperature regime for sparse random graphs. As our running example, we use the Potts and random-cluster models on G(n,d/n) for d=Θ(1), where we show a polynomial-time sampling algorithm for all sufficiently large q and d, at all temperatures. Our approach applies more generally for models that are monotone. Key to our result is a simple polymer definition that blends easily with the connectivity properties of the graph and allows us to show that polymers have size at most O(logn).

Keywords and phrases:
approximate counting, Glauber dynamics, random cluster model, approximate sampling, Erdős-Rényi Graphs
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Gibbs sampling
; Mathematics of computing Random graphs ; Mathematics of computing Markov-chain Monte Carlo methods
Related Version:
A full version with all proofs is available at: https://arxiv.org/abs/2502.08328 [22]
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

We consider the problem of sampling from high-dimensional distributions in the so-called low-temperature regime, which is typically characterised by non-local behaviour. A classical example that has been studied in this context is the problem of sampling independent sets on bipartite graphs where it is perhaps intuitive to expect that a typical independent set is correlated with one of the two sides of the bipartition. Another standard example is the ferromagnetic Potts model on (not necessarily proper) q-colourings weighted by the number of monochromatic edges (see below for definitions) where, at low temperatures, a typical colouring is expected to be correlated with one of the q monochromatic colourings.

Starting from [32, 34], a series of works have demonstrated that this correlation can be utilised to obtain fast sampling algorithms for certain graph classes that exhibit strong expanding properties; perhaps the most prominent graph example is the class of random regular graphs. Lattices (such as d) can also be treated using contour models. By contrast, it is far from clear how to apply this intuition to general graphs. In fact, sampling at low-temperatures is conjectured to be hard on general graphs, captured by so-called #BIS-hardness in the case of the Potts and independent-set examples.

Perhaps the most natural class of graphs that has so far remained elusive from this algorithmic framework is the class of sparse Erdős-Rényi random graphs like 𝒢(n,d/n) for d=Θ(1). This class has actually posed challenges even for high-temperature sampling [39, 16, 9, 3, 17, 43, 40] where the presence of high-degree variables typically complicates the applicability of standard sampling techniques. For low-temperature sampling however the obstacles come primarily from another side, namely from the presence of many small “sparse” parts which have weak, if any, expansion. For example, in 𝒢(n,d/n), this phenomenon not only causes the graph to be disconnected, but even inside the giant component there are induced paths of size roughly Θ(logn) that therefore have almost no expansion; similarly, one can find various other sparse induced components which are scattered inside the giant.

Our main contribution is to develop the polymer method in the low-temperature regime for sparse random graphs. As our running example, we use the Potts and random-cluster models on 𝒢(n,d/n) for d=Θ(1) where we show a polynomial-time sampling algorithm for all sufficiently large q and d at all temperatures. Our approach applies more generally for models that are monotone. Key to our result is a simple polymer definition that blends easily with the connectivity properties of the graph and allows us to show that polymers have size at most O(logn).

To formally state our result, we recall a few standard definitions. The random cluster (RC) model with real parameters q,β>0 is a weighted edge model arising from statistical physics, assigning probabilities to the edge subsets of a given graph G=(V,E). For each edge subset FE, the associated weight of the configuration F is given as

wG(F)=wG;q,β(F)=qc(F)(eβ1)|F|,

where c(F) is the number of components in the graph (V,F). We refer to edges in F as the in-edges of the configuration (and edges in E\F as the out-edges). Denote by ΩG the set of all configurations, i.e., all edge subsets of G. The Gibbs distribution πG=πG;q,β is defined by πG(F)=wG(F)/ZG for FΩG, where ZG=FΩGwG(F) is the partition function. The random cluster model can be viewed as an equivalent edge-representation of the Potts model (when q is an integer), which is supported on vertex assignments σ:V{1,,q} weighted by eβm(σ) where m(σ) is the number of monochromatic edges under σ.

For the random graph 𝒢(n,d/n) which is our focus here, the qualitative structure is conjectured to align with that on the random regular graph that has been extensively studied. In the so-called high temperature regime (low β) a typical configuration is expected to be correlated with the all-out configuration (F=) and to consist of many small components – this set of configurations is known as the “disordered phase”; whereas in the so-called low temperature regime (high β) a typical configuration is expected to be correlated with the all-in configuration (F=E) and to consist of a giant component (and other small components) – this set of configurations is known as the “ordered phase”. The interesting feature of the random-cluster model is that, on several classes of graphs, there is a critical threshold βc where the two phases coexist and each have probability bounded below by a constant. This coexistence typically causes severe complications to sampling in a window around βc, see for example [14, 26, 30] for various metastability phenomena and [29, 25, 10] for computational hardness results that build on this.

Understanding this picture on 𝒢(n,d/n) more precisely is quite a bit more complicated than the random regular graph, even with currently available analysis tools; the key difference is that the local neighbourhood of a vertex is given by a Poisson tree (rather than a regular tree). For example, the value of the log-partition partition function limn1nlogZG for low-temperatures is likely a rather involved expectation over Poisson trees based on understanding fixed-point equations on the underlying set of trees.111This is based on the fact that the model is “replica symmetric” [1]; to the best of our knowledge the formula for the log-partition function has not been established yet. Likewise, understanding the performance of Markov chain algorithms on 𝒢(n,d/n) becomes extremely involved; in fact, even getting a fairly precise understanding of what happens on a Poisson tree for low temperatures is open for both the Potts and random cluster models.

Our main result is to obtain an algorithm for 𝒢(n,d/n) by introducing suitable developments to the polymer framework and showing how to use these together with recent MCMC techniques. As a corollary of our techniques, we obtain various tools for the RC distribution on 𝒢(n,d/n) that shed light on the properties of the distribution.

Theorem 1.

Let d be a large enough real. Then, for all sufficiently large reals q, there is a (randomised) algorithm 𝒜 such that the following holds whp over G𝒢(n,d/n), for any inverse temperature β>0. On input G, with probability at least 3/4, the algorithm 𝒜 outputs in poly(n) time a sample FΩG whose distribution is within TV-distance eΩ(n) from the RC distribution πG;q,β, and an estimate Z^ for the RC partition function ZG=ZG;q,β that satisfies Z^=(1±eΩ(n))ZG.

The success probability of 3/4 in Theorem 1 can be powered in the standard way. As we will describe later in more detail (Section 4), our algorithm is based on running the Glauber dynamics for the random-cluster model from a suitable initial configuration, though it is a bit more involved than that since, in an interval of temperatures [β0,β1], it needs to approximate the appropriate mixture of the ordered and disordered phases.

The running time of the algorithm in Theorem 1 is poly(n) where the implicit constant in the exponent scales as O(logq); this is largely because of a crude polynomial mixing-time bound on Poisson trees with wired boundary (i.e., Poisson trees where the leaves are conditioned to belong to the same component, say by contracting them into a single vertex). It is an open question to obtain sharper bounds with the wired boundary condition, even for regular trees when q is non-integer (cf. [4, Theorem 5]).

The lower bound on q in Theorem 1 is roughly exp(Ω(dlogd)), which is essentially the “standard” bound where polymer-based techniques work (at least on bounded-degree graphs). Having q this large facilitates showing closeness of a typical sample to the extreme configurations. In the case of bounded-degree graphs, there has been some progress in lowering the value of q, mainly on random regular graphs [6, 20]. For large β these results come from first/second moment methods, though these results do not extend to non-integer q or to our G(n,d/n) setting.

We can improve significantly upon the running time using a different (deterministic) algorithm based on estimating the probability that an edge is an in-edge (based on a certain correlation decay property known as weak spatial mixing (WSM) within the phase, see Section 2.3) and integrating the expected number of in-edges. We expect that this different approach to utilising WSM will be useful in other settings where the underlying graph has tree-like neighbourhoods.

Theorem 2.

Let R>0 be arbitrarily large. For all sufficiently large reals d, for all sufficiently large reals q, there is an algorithm  such that the following holds whp over G𝒢(n,d/n), for any temperature β>0. On input G, the algorithm outputs in n1+1R time an estimate Z^ for the RC partition function ZG=ZG;q,β that satisfies Z^=(1±1nR)ZG.

It may help to explain the parameters in Theorem 2. The parameter q controls the accuracy of the algorithm via the decay rate in Lemma 6, and d controls the running time via the length r in Lemma 6 (capturing the size of the polymer). So, for any fixed “target” (captured by R>0), by first taking d large (w.r.t. R), and then taking q large (w.r.t. d), we can make both the running time and the accuracy sufficiently small in terms of the target (as per the theorem statement). See Remark 22 for further comments about the restriction that d be sufficiently large, and how this arises (via Proposition 24) in the proof of Lemma 6.

1.1 Discussion and Further Related Work

Most of the known low-temperature algorithms are based on the so-called polymer method which was developed in [32, 34]. Intuitively, a polymer represents a local part of a configuration that deviates from a certain extremal/ground state. The success of the method typically relies on the Kotecký-Preiss condition [37] that roughly controls the number of polymers and the growth of their weights. This condition guarantees that the log partition function can be approximated by truncating a relevant convergent series expansion (the cluster expansion) and then applying the interpolation techniques of [2, 41]; see also [13] for MCMC variants. The method has been very successful in the low-temperature regime [32, 34, 38, 11, 31, 15, 23, 35, 12, 36].

The main difficulty in applying the polymer method on 𝒢(n,d/n) is that small polymers, such as induced paths of length Θ(logn) or other sparse induced subgraphs present in the graph, can have unusually large weight violating the growth rate required by Kotecký-Preiss type conditions. This difficulty causes undesirable restrictions; for example, [24] worked on a sparse random graph model with degrees 3, a condition that ensures the absence of such non-expanding parts and precludes therefore 𝒢(n,d/n). As we will see in the following section, the main contribution of the present paper is to develop the polymer method for sparse random graphs such as 𝒢(n,d/n) by introducing a suitable polymer definition.

The algorithm provided in our proof of Theorem 1 is based on the Glauber dynamics Markov chain for the random-cluster model. For the case of random regular graphs, the mixing properties of Glauber dynamics are well-studied. Blanca and Gheissari [5] showed that the random cluster Glauber dynamics is mixing in time O(nlogn) for all q2 and β<βu where βu is the uniqueness threshold on the regular tree, and they showed that the same bound applies on 𝒢(n,d/n) as well [8]; see also [7] for mixing-time results on other graph classes that apply for large β. However, for β near the ordered/disordered threshold βc (satisfying βc>βu), the chain undergoes an exponential slowdown due to metastability phenomena and phase coexistence [31, 14]. Our results suggest a similar exponential slowdown around criticality.

However, despite the worst-case mixing result, it is still possible to obtain a fast sampling algorithm based on Glauber dynamics using an appropriate initialisation from a ground state, see [27, 28, 21]. Polymer techniques are helpful in this setting since they can be used to show a notion called weak spatial mixing within a phase introduced in [27], see Section 2.3 for definitions. In the next section, we discuss more thoroughly how to adapt the polymer method for 𝒢(n,d/n) which is the main bottleneck of our results.

1.2 Overview: old and new polymers

As we have noted, polymers capture small, independent deviations from a certain extremal configuration called the “ground state”. For example, for the random cluster model the natural ground states are the all-in and all-out configurations, and for the ferromagnetic Potts model the ground states are the monochromatic colourings.

To apply the polymer framework, the weight of a polymer needs to be defined in a way that enables us to relate the weight of a configuration to the product of weights of its polymers, and thus to relate the probability of a polymer appearing in a configuration to its weight. For models with only local interactions, such as the Potts model, the characterization of these small deviations, i.e., the definition of polymers, is clear from the model. For instance, for the Potts model on low temperatures (high β), a typical configuration has the majority of vertices having the same colour. Thus the natural choice for polymers of a q-colouring σ are maximal connected sets γ which are not coloured with the majority colour. The weight wγ measures how much weight is lost by having bichromatic edges within the polymer γ.

However, when considering how a polymer should be defined for a configuration F of the random cluster model, the answer is not as straightforward. For low-temperatures (high β), the natural ground state is the all-in configuration, thus a natural choice would be to consider (connected) sets of all-out edges. However the random cluster model has long-distance interactions, and in particular, the weight (and thus the probability) of a configuration F depends not only on the number of out-edges (or in-edges), but also on the number of components. For a component of (V,F), it may not be the case that the set of out-edges separating it from the rest of the graph is connected. If multiple polymers are allowed to enclose a single component, it is not clear how to capture that component’s contribution to the weight of the configuration using (multiplicative) polymer weights.

One insightful solution to this problem was given for the case of the random regular graph by Helmuth, Jenssen and Perkins [31], where they iteratively added more edges to the polymers, and then used the strong expansion properties of random regular graphs to ensure the desired multiplicative properties. For completeness, we will define their polymers for a configuration F: Let 0=|EF|. For k0, define inductively k+1 to be the set of edges in k along with all edges incident to vertices that have at least a 59-fraction of their incident edges in k. Then the set of polymer edges is inf(F)=k0k and polymers are connected components of edges in inf. Using the strong expansion of random regular graphs, they show that for any ordered configuration (V,F), there is one giant component containing >n/2 vertices, and every other component has all its incident edges contained in a polymer. While the constant 59 in the definition could be lowered to any 12+τ, to avoid inf(F)=E it has to be greater than a half.

The fact that an ordered configuration has a giant component also applies for 𝒢(n,d/n). However, having the constant 5/9 (or anything larger than 1/2) causes problems in graphs where degrees can be small. For instance, a 3-cycle of a 3-regular graph has expansion 12. Suppose that the edges of the 3-cycle are in-edges, but the edges separating it from the rest of graph are out. Then these separating edges are not necessarily contained in a single polymer. This makes it difficult to capture the component’s contribution, as explained earlier. These problems persist even if the expansion of sufficiently large subgraphs is above 1/2 by any margin.

In the case of 𝒢(n,d/n) the same problem is present in a more severe form: while large-enough connected sets can be shown to have expansion >12 (for d large enough), there are small subgraphs with as many as Θ(logn) vertices with extremely low expansion. These small subgraphs can not be captured by these expansion-based polymers and it is therefore not clear how to extend the polymer definition of [31] for the case of 𝒢(n,d/n).

To start working towards a polymer definition, note that expanding properties of 𝒢(n,d/n) that hold for sets of size Ω(logn) can be used to show that (V,F) contains a giant component and all the other components are small (provided that |F| is sufficiently large relative to |E|). So, a natural-looking solution for the polymer-definition problem is to simply take the polymers of a configuration F to be components formed by the union of the set of out-edges E\F and the set of edges in E incident to vertices in small components of (V,F) (irrespectively of whether they belong to F). While this definition can be endowed with a polymer-weight definition that does satisfy the desired multiplicative properties, these polymers do not capture properly the deviations from the all-in configuration. For instance, suppose there was a connected subgraph S of (V,F) with exactly one in-edge e in the cut (S,S¯). Then it would make sense that vertices of S belonged to a polymer since the removal of a single edge e carves out S as a component, affecting significantly the marginal probability that an edge in the cut (S,S¯) is an in-edge. Now, if the cut (S,S¯) is large, having S as a component in a configuration (after removal of e) is a large deviation from the ordered state and is extremely unlikely to happen, and the marginal probabilities of edges in the cut should not be so sensitive to the status of a single edge. Hence, such “almost-components” must be enclosed in a polymer.

For our analysis specifically, we care about marginals of edges incident to a particular vertex v, thus we do not want the marginals of edges not in a polymer be sensitive to the state of the edges incident to v. Thus, as we show in Section 3, the natural choice of ordered polymers is to take polymer edges to be the union of the set of out-edges of F and the set of edges of G incident to vertices in subgraphs that would be disconnected by removing this vertex v. In Section 3 we show that with good probability the polymers have size O(logn) and we use this to prove weak spatial mixing within the phase. This is then used for bounding the mixing time from the Glauber dynamics (Theorem 1) and converting to the counting algorithm (Theorem 2).

2 Proof Outline of Theorems 1 and 2

2.1 The largest component of the graph

It is well-known that for a graph G with multiple components, the Gibbs distribution πG is a product distribution over the individual components, and that the partition function ZG is the product over the partition function over individual components.

For d>1, 𝒢(n,d/n) whp contains one component of linear size while all remaining components have size O(logn) and contain at most one cycle, see for example [33, Section 5]. We can therefore brute-force O(logn)-sized components by enumerating all possible edge configurations in poly(n) time; in fact, even the mixing time from worst-case initial configuration on such a component is going to be at most poly(n) (see, e.g., [6, Lemma 6.7]).

So, we only need to focus on the largest component of 𝒢(n,d/n), which we denote by C=(VC,EC). Let nC=|VC| be the number of vertices. It is well-known (see e.g. [33, Theorem 5.4]) that nC is determined by the conjugate μ(0,1) of d which satisfies μeμ=ded. Using this, it is not hard to verify that for large d we have whp nC(1ed/3)n and |EC|=dn2±2ned/3, see Appendix A in the full version [22] for details.

For clarity of notation, we use ΩC to denote the set of configurations, wC for the weights of configurations, πC for the Gibbs distribution and ZC for the partition function for the random cluster model on C. For FΩC, we use c(F) to refer to the number of components in (VC,F).

2.2 Phases of random cluster model on 𝓖(𝒏,𝒅/𝒏)

Next, we formally introduce the notion of the ordered and disordered phases on C=C(𝒢(n,d/n)), as well as some necessary notation.

Definition 3 (Phases).

Let η:=1/1000. The ordered phase is ΩCord:={FΩC|F|(1η)|EC|}. The ordered distribution πCord is defined for FΩCord by πCord(F):=wC(F)/ZCord, where ZCord:=FΩCordwC(F). The disordered phase is ΩCdis:={FΩC|F|η|EC|}. The disordered distribution πCdis is defined for FΩCdis by πCdis(F)=wC(F)/ZCdis, where ZCdis:=FΩCdiswC(F).

We will use the following two thresholds for β, β0 and β1, defined from the following:

eβ01=q(21/10)/d and eβ11=q(2+1/10)/d. (1)

Note that the constant 1/10 in the definitions above is somewhat arbitrary and could be decreased to any absolute constant τ>0. The next theorem tells us that a typical configuration on 𝒢(n,d/n) is either ordered or disordered and “far away” from phases’ boundaries. For the proof, see Appendix C in the full version [22].

Theorem 4.

Let d be sufficiently large. Then, for all q sufficiently large, the following holds whp over G𝒢(n,d/n), where F denotes a random configuration from the given distribution.

  1. (1)

    For all β>0, πC(9η10|EC||F|(19η10)|EC|)en.

  2. (2)

    For all ββ0, πCord(|F|(19η10)|EC|)en.

  3. (3)

    For all ββ1, πCdis(9η10|EC||F|)en.

  4. (4)

    For ββ1, πCπCordTV2en.

  5. (5)

    For ββ0, πCπCdisTV2en.

2.3 WSM and proof of Theorem 2 via WSM

The main challenge in order to obtain our results is showing WSM within the phase, which we define more formally here for the linear-sized component. Namely, for a vertex vVC and an integer r, let Br(v) be the ball of radius r around v, i.e. the induced subgraph consisting of all vertices distance r from v. Let πBr(v) denote the Gibbs distribution on B with the free boundary condition (i.e., conditional on all edges outside of Br(v) being out) and πBr+(v) denote the Gibbs distribution on Br(v) with the wired boundary condition (i.e., conditional on all vertices at distance exactly r from v as being wired into a single component). For an edge eEC, we use 1e denote the event that e is an in-edge.

Definition 5.

Let r>0 be an integer and K(0,1) be a real.

We say that C has WSM within the disordered phase at distance r with rate K if for every edge eEC and vertex vVC incident to e, it holds that |πCdis(1e)πBr(v)(1e)|Kr.

Similarly, C has WSM within the ordered phase at distance r with rate K if for every edge eEC and vertex vVC incident to e, it holds that |πCord(1e)πBr+(v)(1e)|Kr.

In Section 3, we show that for all d and q large enough, whp C has WSM within the ordered phase for all ββ0. For the proof of WSM within the disordered phase for all ββ1 see the Appendix B in the full version [22].

Lemma 6.

There is a constant A>0 such that the following holds for all real d sufficiently large. For all q sufficiently large, whp over G𝒢(n,d/n), for all ββ0, the largest component C of G has WSM within the ordered phase at distance r=Adlogn with rate K=q1/30.

Using this, we can prove Theorem 2. To outline briefly the main idea, consider arbitrarily large R>0 and ββ0; then, our goal is to approximate ZC;q,βord in time nO(1/R) within relative error nR. We view ZC;q,βord as a function of β and set gC(β):=logZC;q,βordβ. Note in particular that

gC(β) =ZC;q,βordβZC;q,βord=eβeβ1FΩCord|F|(eβ1)|F|qc(F)ZC;q,βord (2)
=eβeβ1𝐄FπCord[|F|]=eβeβ1eECπC;q,βord(1e).

Moreover, by setting β=n1/R and integrating, we have that

ZC;q,βordZC;q,βord=exp(ββgC(β)dβ). (3)

We will show later that for β=β it holds that ZC;q,βord=(1±enΩ(1/R))q(eβ1)|EC|. So, to obtain the desired approximation to ZC;q,βord, it suffices to approximate the integral I:=ββgC(β)dβ. The standard way to approximate the integral would be to consider a sequence of β’s between β and β and, for each of them, approximate gC(β) using the WSM guarantee. Namely, by Lemma 6, for an edge eEC and a vertex v incident to it, for the ball Be:=Br(v) with r=Adlogn, it holds that

|πC;q,βord(1e)πBe+;q,β(1e)|qr/301nR+3, (4)

where the last inequality follows by taking q large enough (with respect to d). Crucially, Be is a 1-treelike222For a real k, a graph is called k-treelike if it becomes a tree after the removal of at most k edges. graph whose size |VG(Be)| can be bounded by drlogn=nO(1/R); there is a fairly standard recursive way to compute πBe+;q,β(1e) exactly (cf. Lemma 7 below). However, in order to get the desired 1nR relative error guarantee for the integral, we would need roughly nR many β^’s, which would lead to a huge running time.

To obtain a faster algorithm, the key observation is that πBe+;q,β(1e) is an explicit function of β which can be represented using an explicit rational function that can be efficiently computed (using recursions) in time polynomial in |VG(Be)|=nO(1/R). Hence we can essentially perform the integration ββπBe+;q,β(1e) symbolically. A technicality that arises is that we cannot get the exact antiderivative (since in general it will be in terms of algebraic numbers) but rather a numerical approximation to the antiderivative that is within additive 1/2nO(1/R) from its true value for all β[β,β]; all of that however requires only nO(1/R) bits of precision and hence can be carried out in nO(1/R) time.

We next state more formally a few technical lemmas whose proofs can be seen in the Appendix D of the full version [22] and then show how to use them and conclude the proof of Theorem 2. We start with the computation of the marginals of edges in 1-treelike graphs.

Lemma 7.

There is an algorithm that, on input an n-vertex 1-treelike graph T rooted at v, an edge e incident to v and an integer r1, computes in time 24rnO(1) rational functions g+(q,x),g(q,x) so that πBr+(v);q,β(1e)=g+(q,eβ1) and πBr(v);q,β(1e)=g(q,eβ1) for all q,β>0.

The next lemma captures the integration part of the argument. For an integer t, its size is the number of bits needed to represent it, and for a rational w=w1w2 with integers w1,w2, its size is given by adding the sizes of w1 and w2. Moreover, for a polynomial P(x)=i=0ncixi of degree n and rational coefficients, its size is given by n+i=1nsize(ci).

Lemma 8.

There is an algorithm that, on input positive rationals a,b,ε each with size n, and integer polynomials P(x),Q(x) with non-negative coefficients and size n, computes in time poly(n) a number I^ so that I^=I±ε where I=abP(x)Q(x)dx.

Finally, we will need the following estimate for the partition function for very large β.

Lemma 9.

Let d be large enough. For all q sufficiently large, for any arbitrarily small constant ε>0, whp over G𝒢(n,d/n) it holds that ZC;q,βord=(1±enε)q(eβ1)|EC| for any βn2ε.

Proof of Theorem 2.

We follow the argument outlined earlier in order to obtain a 1nR-estimate Z^ord for ZC;q,βord when ββ0. An analogous argument gives an approximation Z^dis for ZC;q,βdis for ββ1 using WSM within the disordered phase (see Proposition 50 in the full version [22]). Then Z^dis is the desired approximation for β<β0, Z^dis+Z^ord for β[β0,β1] and Z^ord for β>β1.

So fix a target ββ0 and focus on approximating ZC;q,βord. Set β=n1/R. If ββ, from Lemma 9 we can use q(eβ1)|EC| as our estimate Z^ord, so we can assume that β<β. From (3) we have that ZC;q,βordZC;q,βord=exp(ββgC(β)dβ) where gC(β)=eβeβ1eECπC;q,βord(1e), cf. (2). From Lemma 9 we can approximate ZC;q,βord with relative error enΩ(1/R) so to obtain the desired approximation to ZC;q,βord, it suffices to approximate the integral I:=ββgC(β)dβ within additive error 1nR+1. For an edge eEC and a vertex v incident to it, let Be=Br(v) with r=Adlogn as in (4) where we saw that WSM gives |πC;q,βord(1e)πBe+;q,β(1e)|qr/301nR+3 for q large enough w.r.t. d. The r-neighbourhoods for G𝒢(n,d/n) are 1-treelike whp (see Lemma 28 in the full version [22]), so by Lemma 7 we can compute in time nO(1/R) a rational function333Here we assume for convenience that q is rational; if q is irrational, the argument can be modified to use instead a rational approximation q^ to q satisfying |q^q|1/2nΘ(1/R). ge(x) so that πBe+;q,β(1e)=ge(eβ1). Therefore for x=eβ1 we have that

|gC(β)x+1xeECge(x)||EC|nR+3, so |IeECxxge(x)xdx||EC|(ββ)nR+3. (5)

Then, using the algorithm in Lemma 8, for each eEC we estimate the integral xxge(x)xdx within additive error 1/nR+3 in time nO(1/R) since each of ge(x)/x and x have size nO(1/R). Combining the estimates gives an |EC|nR+3-estimate of the sum of integrals in (5), yielding a 1nR+1-estimate of the integral I. All in all, this gives the desired 1nR-estimate of ZC;q,βord in time n1+O(1/R). Since R can be arbitrarily large, the theorem follows.

2.4 Graph properties

Before proceeding to the WSM proofs, we use the following expansion properties of 𝒢(n,d/n) (and its largest component). While the random graph lacks regularity and expansion from small sets, for connected subgraphs of size Ω(logn) we can lower bound the average degree and thus obtain a weak expansion property. Since we have two graphs, G and its largest component C, for the clarity of notation, we use VG for the vertex set of G, and EG for its edge set. For the proofs of the following propositions see Appendices A.2 and A.3 in the full version [22].

Proposition 10.

For any ε(0,1), there exists A=A(ε)>0 such that for all d large enough, whp over G𝒢(n,d/n), any connected vertex set SGVG with size at least Alog(n)/d has average degree at least (1ε)d.

In the following proposition, and throughout the paper, we use degG(S) to denote the total degree of a set SVG, that is, degG(S) is the sum of the degrees (in G) of vertices in S. For a subset TVG we write EG(S,T) to denote the set of edges with one endpoint in S and the other in T. We also use eG(S):=|EG(S,S¯)|.

Proposition 11.

There exists a constant A>0, such that for all d large enough, whp over G𝒢(n,d/n) the following holds. Let SVC be a connected vertex set in C with |S|Alog(n)/d and degG(S)110degG(VC). Then eG(S)35degG(S). The same holds if SVC is a connected set in C with Alog(n)/d|S|n/6.

We remark that the choice of 3/5 in Proposition 11 is arbitrary, and any constant between 1/2 and 1 could be used. Also, note that the lower bound Alog(n)/d in both propositions is asymptotically optimal in n and d, as it can be shown that G contains an induced path of length lognd.

Finally, we will use the property that after removing a constant fraction of edges, C still contains a large component. This property is well-known for expanders [42]; to prove it for C we use the fact that its kernel (the graph obtained from C by contracting every induced path into a single edge and removing attached trees) is an expander. The constant 1/144 in the lemma is somewhat arbitrary and follows from the expansion constant for the kernel (see Appendix A in the full version [22]).

Lemma 12.

For all d large enough, whp over G𝒢(n,d/n) the following holds. Suppose that θ(0,12) is a real and EEC is an edge subset such that |E||EC|144(2θ1100). Then (VC,ECE) has a component with total degree degG(VC)(1θ), and all other components of (VC,ECE) have total degree at most θdegG(VC).

In light of Lemma 12, we will order components of any subgraph C of C by their total degree. So we use the phrase “largest component” to refer to the component of C with largest total degree. A “giant” component is a component whose total degree is more than half of the total degree of C, and “small” otherwise. Thus, by applying Lemma 12 for θ=1/10, we have that for any EΩCord the subgraph (VC,E) contains a giant component and all the other components are small.

3 Weak spatial mixing within the ordered phase

In this section, we prove WSM within the ordered phase. We bound the difference of the marginals on e by the probability that, roughly, there is a long path avoiding the giant component of (VC,F). We then use the new definition of ordered polymers that naturally captures this event.

Formally for a vertex v and an integer r1, define 𝒜v,r to be the event, that for a random configuration F, all simple length-r paths from v in GC intersect the largest component of the graph (VC,F)\v, i.e., the graph (VC,F) with v removed. Define 𝒜v,r to be the event that |FEG(Br(v))|(1η)|EC|. Then, we have that

|πBr+(v)(1e)πCord(1e)|2πCord(¬𝒜v,r)+2πCord(¬𝒜v,r). (6)

This follows by conditioning on the boundary configuration outside of Br(v). Namely, using the monotonicity of the RC model, this boundary condition is dominated above by the wired boundary condition on Br(v), where all vertices at the boundary of Br(v) are conditioned to belong to the same component, and hence πCord(1e)πBr+(v)(1e). Likewise, the event 𝒜v,r gives from Lemma 12 that there is a unique giant component CF in the graph (VC\Br(v),F\EC(Br(v))) and Av,r that there is a set S of vertices inside Br(v) whose removal disconnects v from the vertices outside of Br(v) and every wS belongs to CF. Therefore, the event 𝒜v,r𝒜v,r implies that there there is a set S of vertices inside Br(v) whose removal disconnects v from the vertices outside of Br(v) and every wS belongs to CF, i.e., S forms a wired boundary condition closer to v. From monotonicity, it follows that πBr+(v)(1e)πCord(1e𝒜v,r𝒜v,r). Combining these estimates on πBr+(v)(1e) yields (6). (A similar argument can be found in [20, Lemma 5.7].)

It is relatively easy to bound the probability of ¬𝒜v,r under πCord. For large enough d, standard estimates for the neighbourhoods of 𝒢(n,d/n) (see also the Lemma 27 in the full version [22]) guarantee that whp over G𝒢(n,d/n), for any rAdlogn, it holds that |EG(Br(v))|nlogn which is at most η10|EC| for n large enough since |EC|=Ω(n) whp. Hence, by Theorem 4(ii), πCord(¬𝒜v,r)en.

It remains to bound the probability of 𝒜v,r, for which we use ordered polymers.

3.1 Ordered Polymers

We want to bound for each vertex v, and for each rlog(n)/d, the quantity πCord(𝒜v,r). To do so, we need to control the size of “polymers” with respect to a configuration F and a vertex vVC.

We first consider non-giant components in (VC,F)\v; roughly, we will refer to the union of their vertices as the polymer vertices. To form polymers, we will take connected components of these vertices. The details are as follows.

Definition 13 (Ordered polymers).

Fix vVC. Consider FΩCord. For any wVC, define the graph Hv(F,w) as follows.

Hv(F,w):={the component of w in (VC,F),if w=vthe component of w in (VC,F)v,if wv.

Let 𝒱(F,v):={wVCdegG(Hv(F,w))12degG(VC)}. The ordered polymers of F are subgraphs of C. We define two types of ordered polymers, non-singleton polymers and singleton polymers.

  • For each maximal set S𝒱(F,v) that is connected in C, there is a non-singleton polymer. The edge set of this polymer consists of all edges in EC that are incident to vertices in S. The vertex set of this polymer is the set of endpoints of these edges.

  • For each edge eECF that is not an edge of a non-singleton polymer of F, there is a singleton polymers of F consisting of the single edge e.

Let Γvord(F) denote the set of all ordered polymers of F (with respect to v).

As we show in Lemma 16, a giant exists in (VC,F) for all FΩCord.

Definition 14.

Fix vVC. Fix FΩCord and γ=(U,B)Γvord(F). The inner vertices of γ are 𝒱γ:=U𝒱(F,v). The out-edges of γ are the edges in Eout(γ):=(ECF)B and eout(γ)=|Eout(γ)| is the number of out-edges of γ. The weight of γ is wCord(γ):=qc(γ)(eβ1)eout(γ), where c(γ) is the number of components of (VC,ECEout(γ))) with total degree at most (1/2)degG(VC).

Lemma 15 relates the definition of the polymers to the event 𝒜v,r. Later, in Lemma 17, we will also relate the weight of a configuration to the product of weights of its polymers.

Lemma 15.

Fix FΩCord. Let r be a positive integer. Suppose that there is a simple path v0,v1,,vr in C such that none of v1,,vr belongs to the largest component of (VC,F)v0. Then there is a polymer γΓv0ord(F) with {v1,,vr}𝒱γ, hence |𝒱γ|r.

Proof.

Consider i[r]. Since viv0, Hv0(F,vi) is the component of vi in (VC,F)v0. This is not the largest component in (VC,F)v0, so degG(Hv0(F,vi))12degG(VC) by Lemma 12. Now note that the v1,,vr form a path in C so they are contained in a single set S in Definition 13. Thus, there is γΓv0ord(F) with {v1,,vr}𝒱γ.

In order to prove Lemma 17, and to bound the probability that there is a large polymer, we next use Lemma 12 to get an upper bound on a size of an ordered polymer.

Lemma 16.

For all d large enough, whp over G𝒢(n,d/n), the following holds. Fix any vVC. For any FΩCord, (VC,F)v contains a component of degree (1110)degG(VC). Hence in particular, every polymer of γΓvord(F) has degG(𝒱γ)110degG(VC).

Proof.

Let θ=1/10. Whp the maximum degree of G is O(lognloglogn), see e.g. [19, Theorem 3.4]. Since |F|(1η)|EC| and η=1/1000, it follows that the graph (VC,F)\v contains at most |EC|144(2θ1100) edges, so by Lemma 12 it has a component κ of total degree (1110)degG(VC). By Definition 13, none of the vertices in κ is in 𝒱(F,v). Thus degG(𝒱(F,v))110degG(VC), and so in particular any component of 𝒱(F,v) has total degree at most 110degG(𝒱(F,v)).

Finally, we note that for any singleton polymer γΓvord(F), from Definition 14, 𝒱γ=.

We use Lemma 16 to relate the weight of a configuration to the product of weights of its polymers.

Lemma 17.

For all d large enough, whp over G𝒢(n,d/n) the following holds. For any FΩCord and vVC

wC(F)=q(eβ1)|EC|γΓvord(F)wCord(γ).

Proof.

Write

q(eβ1)|EC|γΓvord(F)wCord(γ)=q1+γΓvord(F)c(γ)(eβ1)|EC|γΓvord(F)eout(γ).

Every out-edge of F is in exactly one ordered polymer of F, thus |ECF|=γΓvord(F)eout(γ). It remains to show that c(F)=1+γΓvord(F)c(γ)

By Lemma 16 whp G is such that for all FΩord, (VC,F) contains a giant component with total degree >12degC(GC). The 1-term in the above equality corresponds to the giant. Now consider any non-giant component κ of (VC,F). Its vertices must be in 𝒱(v,F), and thus in 𝒱γ for some γΓvord(F), hence also EC(V(κ),V(κ)¯)Eout(γ). Since κ is connected in (VC,F), it must be connected in (VC,ECEout(γ)), as FECEout(γ), thus it is accounted for in c(γ). Therefore 1+c(F)1+γΓvord(F)c(γ).

Now consider κ to be a non-giant component of (VC,ECEout(γ)) for some γΓvord(F). Since (VC,EC) is connected, Eout(γ) contains an out-edge e incident to some vertex w of κ. Since FECEout(γ), the component of w in (VC,F), κ, must be a subgraph of κ. Clearly, κ must also be non-giant, thus all of its vertices are in 𝒱(v,F). Since non-singleton polymers are maximal connected subgraphs consisting of vertices in 𝒱(v,F), there is a unique polymer γ containing vertices in V(κ)V(κ). Since e is an out-edge incident to w, eEout(γ). Thus e is not in a singleton polymer in Γvord(F), so γ must be a non-singleton polymer with an endpoint of e contained in 𝒱γ. But then 𝒱γ{w} is a connected subset in (VC,EC), and thus in particular so is 𝒱γ𝒱γ. Since polymers of F do not intersect, it must be the case γ=γ and κ=κ. Thus each non-giant component κ of (VC,ECEout(γ)) for any γΓvord(F) is also a non-giant component of (VC,EC) and for any γΓvord(F), γγ, κ is not a non-giant component of (VC,ECEout(γ)). This finished the second part of the equality and thus the proof.

It remains to bound the probability that there is a large polymer. To do so, we show that the weights of (sufficiently large) polymers decay, and then relate the weights to the probabilities that polymers occur.

Observe that for any FΩCord, any vVC and any non-singleton polymer γΓvord(F), all edges in EG(𝒱γ,𝒱γ¯) that are not incident to v are out-edges. To see this, note that, if there is an in-edge from wv𝒱γ¯ to u𝒱γ, then the vertices u and w would be in the same component of Hv(F,w), but then by the definition of non-singleton polymers, w would be in 𝒱γ. Since, for any singleton polymer γ, 𝒱γ=, the same statement applies. Formally we have the following.

Observation 18.

Let FΩCord, vVC and γΓvord(F). Then Eout(γ)EG(𝒱γ,𝒱γ¯)EG(v,𝒱γ), and hence eout(γ)|EG(𝒱γ,𝒱γ¯)||EG(v,𝒱γ)|.

We next use that whp G is 1-treelike, i.e. that for all d large enough, whp any radius-lognd ball in G (and thus in C) can be made into a tree by removing at most a single edge, to show that EG(v,𝒱γ) accounts for a small fraction of edges going from 𝒱γ.

Lemma 19.

For all real d large enough, whp over G𝒢(n,d/n) the following holds. For any vVG and for any connected subset SVG that doesn’t contain v, |EG(v,S)|2+d|S|logn.

Proof.

Let r denote lognd. For all d sufficiently large, whp any radius-r ball in G can be made into a tree by removing at most a single edge. For the proof of this fact, see Lemma 28 in the full version [22]. Let vVG be any vertex. If |EG(v,S)|2, we are done. So assume otherwise (which obviously implies that there is a neighbour of v in S).

Consider the radius-r ball around v in the induced graph on S{v}, and denote it B. Since B is a subgraph of a radius-r ball in G, there is an edge set EG(B) with ||1, such that removing from B makes it a tree.

Let U be the set of neighbours of v in S. Since S is connected and does not contain v, there is a spanning tree T of G[S]. Note that since B is a tree where all vertices of U are adjacent to v, any path between two vertices of U with length 2r in G[S] has to contain the edge in . Therefore, if a component of T contains 2 vertices from U, then its size is at least r. Removing the edge (if any) of from T disconnects it to at most 2 components. Since we assumed |U|=|EG(v,S)|>2, at least |EG(v,S)|1 of the vertices in U are in components of T together. Thus, summing up we obtain |S|(|U|1)r. Rearranging we get that |EG(v,S)|1+max(1,|S|r)2+d|S|logn.

Corollary 20.

For all real d large enough, whp over G𝒢(n,d/n) the following holds. Let vVC, FΩord. Then for any γΓvord(F), it holds that eout(γ)|EG(𝒱γ,𝒱γ¯)|2d|𝒱γ|logn.

Proof.

By Observation 18, any in-edges in EG(𝒱γ,𝒱γ¯) are from 𝒱γ to v. If v𝒱γ, all edges in EG(𝒱γ,𝒱γ¯) are out, so the inequality follows. If v𝒱γ, recall that, for a singleton polymer γ, 𝒱γ= and for a non-singleton polymer γ, 𝒱γ is connected in C. Apply Lemma 19 to show that EG(v,𝒱γ)2+d|𝒱γ|/log(n).

Now we can bound weight of any ordered polymer γ, provided it is large enough, to apply expansion and average degree bounds.

Lemma 21.

There exists a real A>0 such that for all d large enough, and for all real q>1, whp over G𝒢(n,d/n) the following holds for all ββ0. For any FΩCord, vVC and γΓvord(F) with |𝒱γ|Adlogn, it holds that wCord(F)qdegG(𝒱γ)/(20d).

Proof.

By Propositions 10 and 11, there is a real A>0 such that for all d large enough, whp over G, for any connected vertex subset SVC with |S|Alognd, its average degree is at least 3536d. Moreover, if degG(S)110degG(VC), then |EG(S,S¯)|35degG(S). Thus for the rest of this proof, assume that G satisfies these properties.

We first show that for any ordered polymer γ with |𝒱γ|Adlogn,

eout(γ)47degG(𝒱γ). (7)

By Lemma 16, degG(𝒱γ)110degG(VC). Thus by Corollary 20, eout(γ)35degG(𝒱γ)2d|𝒱γ|logn. Finally, 𝒱γ is a connected subset of VC with |Vγ|Adlogn, hence 2+d|𝒱γ|/logndegG(𝒱γ)2+d|𝒱γ|/logn35d|𝒱γ|/36. Since |𝒱γ|=Ω(logn), this fraction is at most 1/35 for sufficiently large n. Thus, eout(γ)degG(𝒱γ)35135=47, concluding the proof of (7).

Recall from Definition 14 that c(γ) is the number of components of (VC,ECEout(γ)) with total degree at most (1/2)degG(VC), that is, the number of small components of (VC,ECEout(γ))).

We first argue that c(γ)|𝒱γ|. Let κ be an arbitrary small component of (VC,ECEout(γ)), we will show that VG(κ)𝒱γ. Since FECEout(γ), all vertices in κ are contained in small components of (VC,F). Thus, from the polymer definition, all vertices of κ are contained in 𝒱(F,v). Since C is connected, the component κ of (VC,ECEout(γ)) has a vertex incident to some edge eEout(γ). Since γ is a non-singleton polymer, the edges of Eout(γ) are all incident to vertices in 𝒱γ, and thus in particular there is w𝒱γ incident to e. Without loss of generality, we may assume that wVG(κ).444If not, then let u be the other endpoint of e. Since it is adjacent to e, uVG(κ) so it is in 𝒱(F,v). But since u𝒱(F,v) and u is an endpoint of e, it is a vertex of γ, so by the definition of 𝒱γ, u𝒱γ. In this case we can just use u as the vertex w. So we can assume wVG(κ). We have also shown already that all vertices of κ are contained in 𝒱(F,v). By construction, 𝒱γ is a maximal subset of 𝒱(F,v) that is connected in C. Since κ contains a vertex w of 𝒱γ, all of its vertices are contained in 𝒱γ, so VG(κ)𝒱γ. Hence, c(γ)|𝒱γ|.

Next, using (7), the average degree bound and the fact that c(γ) is at most |𝒱γ|, we get that

c(γ)eout(γ)|𝒱γ|47degG(𝒱γ)1473536d=95d (8)

To finish the proof, plug (8) and then (7) into the definition of a polymer weight (Definition 14) and use the fact that eβ1q(21/10)/d for ββ0 (See (1)) to obtain:

wCord(γ)=qc(γ)(eβ1)eout(γ)[q95d21/10d]eout(γ)=qeout(γ)/10qdegG(𝒱γ)/(20d).

 Remark 22.

Note that Lemma 21 crucially requires d to be large enough for sufficient expansion and average degree properties to hold for all connected sets of size at least Alogn/d. While expansion properties hold for all d>1 (see e.g. [18]), we must treat sets as large as Alogn/d and for these we require large d to obtain the required average degree properties and to show that the weights of the polymers are sufficiently small.

We next relate the weight of an ordered polymer to the probability of it occurring.

Lemma 23.

For all d large enough, whp over G𝒢(n,d/n) the following holds. For vVC and any γFΩCordΓvord(F), it holds that πCord(γΓvord())wCord(γ).

Proof.

Fix vVC and let γFΩCordΓvord(F). If eout(γ)=0, then since C is connected, wCord(γ)=1, and the inequality is trivial. Thus, for the rest of the proof, assume that Eout(γ). Let ΩCord(γ)={FΩCord;γΓvord(F)} and note that

πord(γΓvord())=FΩCord(γ)wC(F)FΩCordwC(F).

For every ordered F with γΓvord(γ), define F:=FEout(γ)F. We claim that wC(F)=wC(F)/wCord(γ). Clearly, |F|=|F|+|Eout(γ)| since all edges in Eout(γ) are out-edges.

If γ is a singleton polymer, then neither of its endpoints are in small components of (VC,F), thus setting its single edge to be in does not change the number of small components, so c(F)=c(F), and it follows that wC(F)=wC(F)(eβ1)=wC(F)/wCord(γ).

Hence, assume that γ is a non-singleton polymer with Eout(γ) and consider the components of (VC,F) and (VC,F). From Lemma 16, there is exactly one giant component in each of (VC,F) and (VC,F). We claim that the components of (VC,F) are the giant component, together with the small components of (VC,F) that do not contain vertices of 𝒱γ.

To prove the claim, first suppose κ is a small component of (VC,F) not containing vertices of 𝒱γ. We use VG(κ) for the set of vertices of κ. Then no edge from EG(VG(κ),VG(κ)¯) is in Eout(γ), thus κ is a component of (VC,F).

For the other direction, let κ be a small component of (VC,F). The vertices of κ are in small components of (VC,F), so by the definition of 𝒱(F,v), VG(κ)𝒱(F,v). We wish to show that κ is a small component of (VC,F) that does not contain vertices of 𝒱γ.

Suppose for contradiction that 𝒱γVG(κ). Then, by the definition of non-singleton polymers, VG(κ)𝒱γ, resulting in EG(VG(κ),VG(κ)¯)Eout(γ), contradicting the fact that κ is a small component of (VC,F). For the rest of the proof, we can therefore assume that 𝒱γVG(κ)=.

To finish the proof of the claim, we wish to show that κ is a small component of (VC,F). Since (VC,F) is a subgraph of (VC,F), there is a non-empty subgraph κ of κ which is a component of (VC,F). Suppose for contradiction that VG(κ)VG(κ). Since κ is connected in F, there exists an edge e={w,u} where wVG(κ)VG(κ) and uVG(κ). But then e must be an in-edge for F but not for F, hence eEout(γ). By the definition of non-singleton polymers, either w or u is in 𝒱γ. Both w and u are in VG(κ) so we have contradicted 𝒱γVG(κ)=, which we have already shown. Thus κ=κ, which concludes the proof of the claim.

By the claim, c(F)c(F) is the number of small components of (VC,F) that contain vertices of 𝒱γ. By the definition of polymers this is exactly c(γ), so by the definition of polymer weights wC(F)=qc(F)(eβ1)|F|=wC(F)(eβ1)eout(F)qc(γ)=wC(F)wCord(γ).

For every FΩCord(γ), both F and F are in ΩCord. Furthermore, FΩCord(γ) and for any distinct F1,F2ΩCord(γ), F1 and F2 are distinct. Thus

πord(γΓvord())=FΩCord(γ)wC(F)FΩCordwC(F)FΩCord(γ)wC(F)FΩCord(γ)(wC(F)+wC(F)).

Hence we can write

πord(γΓvord())FΩCord(γ)wC(F)FΩCord(γ)(wC(F)+wC(F))FΩCord(γ)wC(F)FΩCord(γ)wC(F)(1+1/wCord(γ)),

which is 11+1/wCord(γ)wCord(γ).

With this in hand, we can show an analogue of the Kotecký-Preiss condition for our ordered polymers (but only considering those that are large enough). We will use this to bound the probability of a large polymer occurring.

Proposition 24.

There is a real A>0 such that for all d large enough, for all sufficiently large reals q, the following holds whp over G𝒢(n,d/n) for all real ββ0. For any vVC,

πCord(γΓvord() with |𝒱γ|Adlogn)qA25dlogn.

Proof.

By Proposition 10 and Lemma 21, there is a constant A such that whp any connected vertex set with size at least Alognd has average degree at least 910d, and any ordered polymer γ with |𝒱γ|Alognd has wCord(γ)qdegF(𝒱γ)/(20d). Also whp the bound from Lemma 23 holds.

Let Γvord=FΩCordΓvord(F). By a union bound and Lemma 23 it is enough to show

γΓvord;|𝒱γ|Alogn/dwCord(γ)qAlogn/(25d).

Start by using the bound on the polymer weights from Lemma 21 to show that

γΓvord;|𝒱γ|Alogn/dwCord(γ)γΓvord;|𝒱γ|Alogn/dqdegG(𝒱γ)/(20d).

Then note that any γ in this sum has |𝒱γ|Alogn/d hence by Proposition 10 it has average degree at least 910d hence degree at least 9A10logn. Thus, the sum is at most

D9A10lognγΓvord;degG(𝒱γ)=DqdegG(𝒱γ)/(20d)

Now we bound the number of polymers of the given total degree D. There are n(2e)2D1 connected subgraphs of total degree D in any graph (see e.g. [24, Lemma 6]). For any connected subset SVC of total degree D, there are at most D edges incident to its vertices, thus there are at most 2D polymers γ with 𝒱γ=S (each of its edges can be either in or out). Thus the sum is at most

D9Alogn/10n(2e)2D12DqD/(20d).

For all q sufficiently large, 8e2q1/(20d)q1/(22d), so the sum is O(nq9Alogn/(220d)). For q sufficiently large, this is qAlogn/(25d).

Proposition 24, Lemma 15 and equation (6) together with the bound from Theorem 4 now directly give Lemma 6, i.e. WSM within the ordered phase at the distance r=Alognd (for some constant A – take twice the constant from the the Proposition 24 to take into account that we want to avoid polymers of size r1).

4 Fast convergence of the RC dynamics and proof of Theorem 1

In order to prove Theorem 1, we use the RC dynamics (Xt)t0 to obtain samples from the ordered and the disordered phases separately. For the sake of completeness, recall that a transition from Xt to Xt+1 is done as follows:

  1. (1)

    Pick an edge eE uniformly at random

  2. (2)

    If e is a cut edge of the graph (V,Xt{e}), then with probability p^:=eβeβ+q1 set Xt+1:=Xt{e}. With all remaining probability set Xt+1:=Xt{e}

  3. (3)

    Otherwise, with probability p:=1eβ, set Xt+1:=Xt{e}. With all remaining probability set Xt+1:=Xt{e}.

Proving mixing of the RC dynamics (Xt) is in general a challenging task, especially since its moves depend on the current component structure. Fortunately, by now there is a well-established strategy [27, 21, 20] that we can use to show the convergence bounds of Theorems 25 and 26 based on the polymer sizes. It consists of utilising the following two main ingredients: (i) weak spatial mixing within a phase (WSM) that as we saw asserts that the marginal probability of an edge e being an in-edge depends only on a small neighbourhood around e, and (ii) the mixing time of the dynamics on that neighbourhood is polynomial in its size. Ingredient (ii) is fairly straightforward in sparse random graphs since small-distance neighbourhoods are typically tree-like (i.e., they contain at most a constant number of cycles) which makes poly-time bounds relatively simple to obtain.

Theorem 25.

Let d be sufficiently large. Then, for all q sufficiently large, whp over G𝒢(n,d/n), for all ββ1 and ε>eΩ(n), the random cluster dynamics Xt initialized from all-out satisfies XTπCdisε for T=O(nlognlog1ε).

Theorem 26.

Let d be sufficiently large. Then, for all q sufficiently large, whp over G𝒢(n,d/n), for all ββ0 and ε>eΩ(n), the random cluster dynamics Xt initialized from all-in satisfies XTπCordε for T=poly(n,log1ε)

Proof of Theorem 1.

For ββ0 and ββ1, it follows from Theorems 4, 25 and 26 that we can get an eΩ(n)-sample by initializing the Glauber dynamics from all-out or all-in respectively.

Note that both theorems give mixing even for β that depends on n. We use this to obtain the an approximation for ZC and hence mixing for β(β0,β1). By considering a sequence of β’s we can approximate ZCord and ZCdis within (1±eΩ(n))-factor using standard self-reducibility techniques (for more details see e.g. [13, 3]), and thus, by Theorem 4 get a (1±eΩ(n)) approximation for ZC. For β(β0,β1), we then obtain an eΩ(n) sample by starting in the appropriate random mixture of all-in and all-out. Given WSM within the phases and using the monotonicity of the random-cluster model, we complete the proof of Theorems 25 and 26 in Appendix E in the full version [22].

References

  • [1] Jean Barbier, Chun Lam Chan, and Nicolas Macris. Concentration of Multi-overlaps for Random Dilute Ferromagnetic Spin Models. Journal of Statistical Physics, 180(1-6):534–557, December 2019.
  • [2] A. Barvinok. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics. Springer International Publishing, 2017.
  • [3] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. Fast sampling via spectral independence beyond bounded-degree graphs. ACM Trans. Algorithms, 20(1), 2024. doi:10.1145/3631354.
  • [4] Antonio Blanca, Zongchen Chen, Daniel ŠtefankoviČ, and Eric Vigoda. The Swendsen–Wang dynamics on trees. Random Structures & Algorithms, 62(4):791–831, 2023.
  • [5] Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, and Kuan Yang. Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. SIAM Journal on Discrete Mathematics, 34(1):742–793, 2020. doi:10.1137/18M1219722.
  • [6] Antonio Blanca and Reza Gheissari. Random-cluster dynamics on random regular graphs in tree uniqueness. Communications in Mathematical Physics, 386(2):1243–1287, 2021.
  • [7] Antonio Blanca and Reza Gheissari. On the tractability of sampling from the Potts model at low temperatures via Swendsen-Wang dynamics. CoRR, abs/2304.03182, 2023. doi:10.48550/arXiv.2304.03182.
  • [8] Antonio Blanca and Reza Gheissari. Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics. The Annals of Applied Probability, 33(6B):4997–5049, 2023.
  • [9] Antonio Blanca and Xusheng Zhang. Rapid mixing of global markov chains via spectral independence: The unbounded degree case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, volume 275, pages 53:1–53:19, 2023. doi:10.4230/LIPICS.APPROX/RANDOM.2023.53.
  • [10] Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda. #bis-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690–711, 2016. doi:10.1016/J.JCSS.2015.11.009.
  • [11] Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, and Corrine Yap. Algorithms for the ferromagnetic Potts model on expanders. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 344–355, 2022. doi:10.1109/FOCS54457.2022.00040.
  • [12] Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A spectral approach to approximately counting independent sets in dense bipartite graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297, pages 35:1–35:18, 2024. doi:10.4230/LIPICS.ICALP.2024.35.
  • [13] Zongchen Chen, Andreas Galanis, Leslie A. Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via Markov chains. Random Structures & Algorithms, 58(2):294–321, 2021. doi:10.1002/RSA.20968.
  • [14] Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts ferromagnet on random regular graphs. Communications in Mathematical Physics, pages 1–41, 2023.
  • [15] Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical Physics Approaches to Unique Games. In 35th Computational Complexity Conference (CCC 2020), volume 169, pages 13:1–13:27, 2020. doi:10.4230/LIPICS.CCC.2020.13.
  • [16] Charilaos Efthymiou and Weiming Feng. On the mixing time of Glauber dynamics for the hard-core and related models on g(n,d/n). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261, pages 54:1–54:17, 2023. doi:10.4230/LIPICS.ICALP.2023.54.
  • [17] Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Sampling random colorings of sparse random graphs. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1759–1771, 2018. doi:10.1137/1.9781611975031.115.
  • [18] Nikolaos Fountoulakis and Bruce Reed. The evolution of the mixing rate, 2007. arXiv:math/0701474.
  • [19] Alan Frieze and Michał Karoński. Introduction to Random Graphs. Cambridge University Press, 2015.
  • [20] Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Planting and MCMC sampling from the Potts model, 2024. doi:10.48550/arXiv.2410.14409.
  • [21] Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Sampling from the random cluster model on random regular graphs at all temperatures via glauber dynamics. Combinatorics, Probability and Computing, pages 1–33, 2024.
  • [22] Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Low-temperature sampling on sparse random graphs, 2025. doi:10.48550/arXiv.2502.08328.
  • [23] Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast algorithms for general spin systems on bipartite expanders. ACM Trans. Comput. Theory, 13(4), September 2021. doi:10.1145/3470865.
  • [24] Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast mixing via polymers for random graphs with unbounded degree. Information and Computation, 285, 2022. doi:10.1016/J.IC.2022.104894.
  • [25] Andreas Galanis, Daniel Štefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #bis-hardness and related results. SIAM Journal on Computing, 45(6):2004–2065, 2016. doi:10.1137/140997580.
  • [26] Reza Gheissari, Eyal Lubetzky, and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen–Wang dynamics. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 56(1):68–86, 2020.
  • [27] Reza Gheissari and Alistair Sinclair. Low-temperature Ising dynamics with random initializations. In 54th Annual ACM SIGACT Symposium on Theory of Computing, (STOC ’22), pages 1445–1458, 2022. doi:10.1145/3519935.3519964.
  • [28] Reza Gheissari and Alistair Sinclair. Spatial mixing and the random-cluster dynamics on lattices. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA ’23) , pages 4606–4621, 2023. doi:10.1137/1.9781611977554.CH174.
  • [29] Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59(5):1–31, 2012. doi:10.1145/2371656.2371660.
  • [30] Vivek K Gore and Mark R Jerrum. The Swendsen-Wang process does not always mix rapidly. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 674–681, 1997. doi:10.1145/258533.258662.
  • [31] Tyler Helmuth, Matthew Jenssen, and Will Perkins. Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs. Annales de l’Institut Henri Poincare (B) Probabilites et statistiques, 59(2):817–848, 2023.
  • [32] Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, , (STOC ’19) , pages 1009–1020, 2019. doi:10.1145/3313276.3316305.
  • [33] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. John Wiley & Sons, Inc., 2000 - 2000.
  • [34] Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs. SIAM Journal on Computing, 49(4):681–710, 2020. doi:10.1137/19M1286669.
  • [35] Matthew Jenssen, Will Perkins, and Aditya Potukuchi. Approximately counting independent sets in bipartite graphs via graph containers. Random Structures & Algorithms, 63(1):215–241, 2023. doi:10.1002/RSA.21145.
  • [36] Matthew Jenssen, Will Perkins, Aditya Potukuchi, and Michael Simkin. Sampling, counting, and large deviations for triangle-free graphs near the critical density. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 151–165, 2024. doi:10.1109/FOCS61266.2024.00020.
  • [37] R. Kotecký and D. Preiss. Cluster expansion for abstract polymer models. Comm. Math. Phys., 103(3):491–498, 1986.
  • [38] Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145, pages 34:1–34:12, 2019. doi:10.4230/LIPICS.APPROX-RANDOM.2019.34.
  • [39] Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu. Fast mixing in sparse random Ising models. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 120–128, 2024. doi:10.1109/FOCS61266.2024.00018.
  • [40] Elchanan Mossel and Allan Sly. Exact thresholds for Ising Gibbs samplers on general graphs. The Annals of Probability, 41(1):294–328, 2013.
  • [41] Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for functions and graph polynomials. SIAM Journal on Computing, 46(6):1893–1919, 2017.
  • [42] Luca Trevisan. Lecture notes on graph partitioning, expanders and spectral methods, 2016. URL: https://lucatrevisan.github.io/books/expanders-2016.pdf.
  • [43] Yitong Yin and Chihao Zhang. Sampling in Potts model on sparse random graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), volume 60, pages 47:1–47:22, 2016. doi:10.4230/LIPICS.APPROX-RANDOM.2016.47.