Low-Temperature Sampling on Sparse Random Graphs††thanks: 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.
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 -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 for , where we show a polynomial-time sampling algorithm for all sufficiently large and , 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 .
Keywords and phrases:
approximate counting, Glauber dynamics, random cluster model, approximate sampling, Erdős-Rényi GraphsCategory:
Track A: Algorithms, Complexity and GamesCopyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Mathematics of computing Gibbs sampling ; Mathematics of computing Random graphs ; Mathematics of computing Markov-chain Monte Carlo methodsRelated 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 PuppisSeries and Publisher:

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) -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 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 ) 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 for . 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 , this phenomenon not only causes the graph to be disconnected, but even inside the giant component there are induced paths of size roughly ) 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 for where we show a polynomial-time sampling algorithm for all sufficiently large and 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 .
To formally state our result, we recall a few standard definitions. The random cluster (RC) model with real parameters is a weighted edge model arising from statistical physics, assigning probabilities to the edge subsets of a given graph . For each edge subset , the associated weight of the configuration is given as
where is the number of components in the graph . We refer to edges in as the in-edges of the configuration (and edges in as the out-edges). Denote by the set of all configurations, i.e., all edge subsets of . The Gibbs distribution is defined by for where is the partition function. The random cluster model can be viewed as an equivalent edge-representation of the Potts model (when is an integer), which is supported on vertex assignments weighted by where is the number of monochromatic edges under .
For the random graph 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 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 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 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 , 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 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 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 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 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 that shed light on the properties of the distribution.
Theorem 1.
Let be a large enough real. Then, for all sufficiently large reals , there is a (randomised) algorithm such that the following holds whp over , for any inverse temperature . On input , with probability at least , the algorithm outputs in time a sample whose distribution is within TV-distance from the RC distribution , and an estimate for the RC partition function that satisfies .
The success probability of 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 , it needs to approximate the appropriate mixture of the ordered and disordered phases.
The running time of the algorithm in Theorem 1 is where the implicit constant in the exponent scales as ; 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 is non-integer (cf. [4, Theorem 5]).
The lower bound on in Theorem 1 is roughly , which is essentially the “standard” bound where polymer-based techniques work (at least on bounded-degree graphs). Having 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 , 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 or to our 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 be arbitrarily large. For all sufficiently large reals , for all sufficiently large reals , there is an algorithm such that the following holds whp over , for any temperature . On input , the algorithm outputs in time an estimate for the RC partition function that satisfies .
It may help to explain the parameters in Theorem 2. The parameter controls the accuracy of the algorithm via the decay rate in Lemma 6, and controls the running time via the length in Lemma 6 (capturing the size of the polymer). So, for any fixed “target” (captured by ), by first taking large (w.r.t. ), and then taking large (w.r.t. ), 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 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 is that small polymers, such as induced paths of length 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 , a condition that ensures the absence of such non-expanding parts and precludes therefore . 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 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 for all and where is the uniqueness threshold on the regular tree, and they showed that the same bound applies on 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 (satisfying ), 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 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 -colouring are maximal connected sets which are not coloured with the majority colour. The weight 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 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 depends not only on the number of out-edges (or in-edges), but also on the number of components. For a component of , 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 : Let . For , define inductively to be the set of edges in along with all edges incident to vertices that have at least a -fraction of their incident edges in . Then the set of polymer edges is and polymers are connected components of edges in . Using the strong expansion of random regular graphs, they show that for any ordered configuration , there is one giant component containing vertices, and every other component has all its incident edges contained in a polymer. While the constant in the definition could be lowered to any , to avoid it has to be greater than a half.
The fact that an ordered configuration has a giant component also applies for . However, having the constant (or anything larger than ) causes problems in graphs where degrees can be small. For instance, a -cycle of a -regular graph has expansion . Suppose that the edges of the -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 by any margin.
In the case of the same problem is present in a more severe form: while large-enough connected sets can be shown to have expansion (for large enough), there are small subgraphs with as many as 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 .
To start working towards a polymer definition, note that expanding properties of that hold for sets of size can be used to show that contains a giant component and all the other components are small (provided that is sufficiently large relative to ). So, a natural-looking solution for the polymer-definition problem is to simply take the polymers of a configuration to be components formed by the union of the set of out-edges and the set of edges in incident to vertices in small components of (irrespectively of whether they belong to ). 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 of with exactly one in-edge in the cut . Then it would make sense that vertices of belonged to a polymer since the removal of a single edge carves out as a component, affecting significantly the marginal probability that an edge in the cut is an in-edge. Now, if the cut is large, having as a component in a configuration (after removal of ) 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 , thus we do not want the marginals of edges not in a polymer be sensitive to the state of the edges incident to . 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 and the set of edges of incident to vertices in subgraphs that would be disconnected by removing this vertex . In Section 3 we show that with good probability the polymers have size 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 with multiple components, the Gibbs distribution is a product distribution over the individual components, and that the partition function is the product over the partition function over individual components.
For , whp contains one component of linear size while all remaining components have size and contain at most one cycle, see for example [33, Section 5]. We can therefore brute-force -sized components by enumerating all possible edge configurations in time; in fact, even the mixing time from worst-case initial configuration on such a component is going to be at most (see, e.g., [6, Lemma 6.7]).
So, we only need to focus on the largest component of , which we denote by . Let be the number of vertices. It is well-known (see e.g. [33, Theorem 5.4]) that is determined by the conjugate of which satisfies . Using this, it is not hard to verify that for large we have whp and , see Appendix A in the full version [22] for details.
For clarity of notation, we use to denote the set of configurations, for the weights of configurations, for the Gibbs distribution and for the partition function for the random cluster model on . For , we use to refer to the number of components in .
2.2 Phases of random cluster model on
Next, we formally introduce the notion of the ordered and disordered phases on , as well as some necessary notation.
Definition 3 (Phases).
Let . The ordered phase is . The ordered distribution is defined for by , where . The disordered phase is . The disordered distribution is defined for by , where .
We will use the following two thresholds for , and , defined from the following:
(1) |
Note that the constant in the definitions above is somewhat arbitrary and could be decreased to any absolute constant . The next theorem tells us that a typical configuration on 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 be sufficiently large. Then, for all sufficiently large, the following holds whp over , where denotes a random configuration from the given distribution.
-
(1)
For all , .
-
(2)
For all , .
-
(3)
For all , .
-
(4)
For , .
-
(5)
For , .
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 and an integer , let be the ball of radius around , i.e. the induced subgraph consisting of all vertices distance from . Let denote the Gibbs distribution on with the free boundary condition (i.e., conditional on all edges outside of being out) and denote the Gibbs distribution on with the wired boundary condition (i.e., conditional on all vertices at distance exactly from as being wired into a single component). For an edge , we use denote the event that is an in-edge.
Definition 5.
Let be an integer and be a real.
We say that has WSM within the disordered phase at distance with rate if for every edge and vertex incident to , it holds that .
Similarly, has WSM within the ordered phase at distance with rate if for every edge and vertex incident to , it holds that
In Section 3, we show that for all and large enough, whp has WSM within the ordered phase for all . For the proof of WSM within the disordered phase for all see the Appendix B in the full version [22].
Lemma 6.
There is a constant such that the following holds for all real sufficiently large. For all sufficiently large, whp over , for all , the largest component of has WSM within the ordered phase at distance with rate .
Using this, we can prove Theorem 2. To outline briefly the main idea, consider arbitrarily large and ; then, our goal is to approximate in time within relative error . We view as a function of and set . Note in particular that
(2) | ||||
Moreover, by setting and integrating, we have that
(3) |
We will show later that for it holds that . So, to obtain the desired approximation to , it suffices to approximate the integral . The standard way to approximate the integral would be to consider a sequence of ’s between and and, for each of them, approximate using the WSM guarantee. Namely, by Lemma 6, for an edge and a vertex incident to it, for the ball with , it holds that
(4) |
where the last inequality follows by taking large enough (with respect to ). Crucially, is a 1-treelike222For a real , a graph is called -treelike if it becomes a tree after the removal of at most edges. graph whose size can be bounded by ; there is a fairly standard recursive way to compute exactly (cf. Lemma 7 below). However, in order to get the desired relative error guarantee for the integral, we would need roughly many ’s, which would lead to a huge running time.
To obtain a faster algorithm, the key observation is that 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 . Hence we can essentially perform the integration 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 from its true value for all ; all of that however requires only bits of precision and hence can be carried out in 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 -vertex 1-treelike graph rooted at , an edge incident to and an integer , computes in time rational functions so that and for all .
The next lemma captures the integration part of the argument. For an integer , its size is the number of bits needed to represent it, and for a rational with integers , its size is given by adding the sizes of and . Moreover, for a polynomial of degree and rational coefficients, its size is given by .
Lemma 8.
There is an algorithm that, on input positive rationals each with size , and integer polynomials with non-negative coefficients and size , computes in time a number so that where .
Finally, we will need the following estimate for the partition function for very large .
Lemma 9.
Let be large enough. For all sufficiently large, for any arbitrarily small constant , whp over it holds that for any .
Proof of Theorem 2.
We follow the argument outlined earlier in order to obtain a -estimate for when . An analogous argument gives an approximation for for using WSM within the disordered phase (see Proposition 50 in the full version [22]). Then is the desired approximation for , for and for .
So fix a target and focus on approximating . Set . If , from Lemma 9 we can use as our estimate , so we can assume that . From (3) we have that where , cf. (2). From Lemma 9 we can approximate with relative error so to obtain the desired approximation to , it suffices to approximate the integral within additive error . For an edge and a vertex incident to it, let with as in (4) where we saw that WSM gives for large enough w.r.t. . The -neighbourhoods for are 1-treelike whp (see Lemma 28 in the full version [22]), so by Lemma 7 we can compute in time a rational function333Here we assume for convenience that is rational; if is irrational, the argument can be modified to use instead a rational approximation to satisfying . so that . Therefore for we have that
(5) |
Then, using the algorithm in Lemma 8, for each we estimate the integral within additive error in time since each of and have size . Combining the estimates gives an -estimate of the sum of integrals in (5), yielding a -estimate of the integral . All in all, this gives the desired -estimate of in time . Since can be arbitrarily large, the theorem follows.
2.4 Graph properties
Before proceeding to the WSM proofs, we use the following expansion properties of (and its largest component). While the random graph lacks regularity and expansion from small sets, for connected subgraphs of size we can lower bound the average degree and thus obtain a weak expansion property. Since we have two graphs, and its largest component , for the clarity of notation, we use for the vertex set of , and 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 , there exists such that for all large enough, whp over , any connected vertex set with size at least has average degree at least .
In the following proposition, and throughout the paper, we use to denote the total degree of a set , that is, is the sum of the degrees (in ) of vertices in . For a subset we write to denote the set of edges with one endpoint in and the other in . We also use .
Proposition 11.
There exists a constant , such that for all large enough, whp over the following holds. Let be a connected vertex set in with and . Then . The same holds if is a connected set in with .
We remark that the choice of in Proposition 11 is arbitrary, and any constant between and could be used. Also, note that the lower bound in both propositions is asymptotically optimal in and , as it can be shown that contains an induced path of length .
Finally, we will use the property that after removing a constant fraction of edges, still contains a large component. This property is well-known for expanders [42]; to prove it for we use the fact that its kernel (the graph obtained from by contracting every induced path into a single edge and removing attached trees) is an expander. The constant 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 large enough, whp over the following holds. Suppose that is a real and is an edge subset such that . Then has a component with total degree , and all other components of have total degree at most .
In light of Lemma 12, we will order components of any subgraph of by their total degree. So we use the phrase “largest component” to refer to the component of with largest total degree. A “giant” component is a component whose total degree is more than half of the total degree of , and “small” otherwise. Thus, by applying Lemma 12 for , we have that for any the subgraph 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 by the probability that, roughly, there is a long path avoiding the giant component of . We then use the new definition of ordered polymers that naturally captures this event.
Formally for a vertex and an integer , define to be the event, that for a random configuration , all simple length- paths from in intersect the largest component of the graph , i.e., the graph with removed. Define to be the event that . Then, we have that
(6) |
This follows by conditioning on the boundary configuration outside of . Namely, using the monotonicity of the RC model, this boundary condition is dominated above by the wired boundary condition on , where all vertices at the boundary of are conditioned to belong to the same component, and hence . Likewise, the event gives from Lemma 12 that there is a unique giant component in the graph and that there is a set of vertices inside whose removal disconnects from the vertices outside of and every belongs to . Therefore, the event implies that there there is a set of vertices inside whose removal disconnects from the vertices outside of and every belongs to , i.e., forms a wired boundary condition closer to . From monotonicity, it follows that . Combining these estimates on yields (6). (A similar argument can be found in [20, Lemma 5.7].)
It is relatively easy to bound the probability of under . For large enough , standard estimates for the neighbourhoods of (see also the Lemma 27 in the full version [22]) guarantee that whp over , for any , it holds that which is at most for large enough since whp. Hence, by Theorem 4(ii), .
It remains to bound the probability of , for which we use ordered polymers.
3.1 Ordered Polymers
We want to bound for each vertex , and for each , the quantity . To do so, we need to control the size of “polymers” with respect to a configuration and a vertex .
We first consider non-giant components in ; 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 . Consider . For any , define the graph as follows.
Let . The ordered polymers of are subgraphs of . We define two types of ordered polymers, non-singleton polymers and singleton polymers.
-
For each maximal set that is connected in , there is a non-singleton polymer. The edge set of this polymer consists of all edges in that are incident to vertices in . The vertex set of this polymer is the set of endpoints of these edges.
-
For each edge that is not an edge of a non-singleton polymer of , there is a singleton polymers of consisting of the single edge .
Let denote the set of all ordered polymers of (with respect to ).
As we show in Lemma 16, a giant exists in for all .
Definition 14.
Fix . Fix and . The inner vertices of are . The out-edges of are the edges in and is the number of out-edges of . The weight of is , where is the number of components of with total degree at most .
Lemma 15 relates the definition of the polymers to the event . Later, in Lemma 17, we will also relate the weight of a configuration to the product of weights of its polymers.
Lemma 15.
Fix . Let be a positive integer. Suppose that there is a simple path in such that none of belongs to the largest component of . Then there is a polymer with , hence .
Proof.
Consider . Since , is the component of in . This is not the largest component in , so by Lemma 12. Now note that the form a path in so they are contained in a single set in Definition 13. Thus, there is with .
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 large enough, whp over , the following holds. Fix any . For any , contains a component of degree . Hence in particular, every polymer of has .
Proof.
Let . Whp the maximum degree of is , see e.g. [19, Theorem 3.4]. Since and , it follows that the graph contains at most edges, so by Lemma 12 it has a component of total degree . By Definition 13, none of the vertices in is in . Thus , and so in particular any component of has total degree at most .
Finally, we note that for any singleton polymer , 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 large enough, whp over the following holds. For any and
Proof.
Write
Every out-edge of is in exactly one ordered polymer of , thus . It remains to show that
By Lemma 16 whp is such that for all , contains a giant component with total degree . The -term in the above equality corresponds to the giant. Now consider any non-giant component of . Its vertices must be in , and thus in for some , hence also . Since is connected in , it must be connected in , as , thus it is accounted for in . Therefore .
Now consider to be a non-giant component of for some . Since is connected, contains an out-edge incident to some vertex of . Since , the component of in , , must be a subgraph of . Clearly, must also be non-giant, thus all of its vertices are in . Since non-singleton polymers are maximal connected subgraphs consisting of vertices in , there is a unique polymer containing vertices in . Since is an out-edge incident to , . Thus is not in a singleton polymer in , so must be a non-singleton polymer with an endpoint of contained in . But then is a connected subset in , and thus in particular so is . Since polymers of do not intersect, it must be the case and . Thus each non-giant component of for any is also a non-giant component of and for any , , is not a non-giant component of . 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 , any and any non-singleton polymer , all edges in that are not incident to are out-edges. To see this, note that, if there is an in-edge from to , then the vertices and would be in the same component of , but then by the definition of non-singleton polymers, would be in . Since, for any singleton polymer , , the same statement applies. Formally we have the following.
Observation 18.
Let , and . Then , and hence .
We next use that whp is 1-treelike, i.e. that for all large enough, whp any radius- ball in (and thus in ) can be made into a tree by removing at most a single edge, to show that accounts for a small fraction of edges going from .
Lemma 19.
For all real large enough, whp over the following holds. For any and for any connected subset that doesn’t contain ,
Proof.
Let denote . For all sufficiently large, whp any radius- ball in 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 be any vertex. If , we are done. So assume otherwise (which obviously implies that there is a neighbour of in ).
Consider the radius- ball around in the induced graph on , and denote it . Since is a subgraph of a radius- ball in , there is an edge set with , such that removing from makes it a tree.
Let be the set of neighbours of in . Since is connected and does not contain , there is a spanning tree of . Note that since is a tree where all vertices of are adjacent to , any path between two vertices of with length in has to contain the edge in . Therefore, if a component of contains vertices from , then its size is at least . Removing the edge (if any) of from disconnects it to at most components. Since we assumed , at least of the vertices in are in components of together. Thus, summing up we obtain Rearranging we get that .
Corollary 20.
For all real large enough, whp over the following holds. Let , . Then for any , it holds that .
Proof.
By Observation 18, any in-edges in are from to . If , all edges in are out, so the inequality follows. If , recall that, for a singleton polymer , and for a non-singleton polymer , is connected in . Apply Lemma 19 to show that .
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 such that for all large enough, and for all real , whp over the following holds for all . For any , and with , it holds that .
Proof.
By Propositions 10 and 11, there is a real such that for all large enough, whp over , for any connected vertex subset with , its average degree is at least . Moreover, if , then . Thus for the rest of this proof, assume that satisfies these properties.
We first show that for any ordered polymer with ,
(7) |
By Lemma 16, . Thus by Corollary 20, . Finally, is a connected subset of with , hence . Since , this fraction is at most for sufficiently large . Thus, , concluding the proof of (7).
Recall from Definition 14 that is the number of components of with total degree at most , that is, the number of small components of .
We first argue that . Let be an arbitrary small component of , we will show that . Since , all vertices in are contained in small components of . Thus, from the polymer definition, all vertices of are contained in . Since is connected, the component of has a vertex incident to some edge . Since is a non-singleton polymer, the edges of are all incident to vertices in , and thus in particular there is incident to . Without loss of generality, we may assume that .444If not, then let be the other endpoint of . Since it is adjacent to , so it is in . But since and is an endpoint of , it is a vertex of , so by the definition of , . In this case we can just use as the vertex . So we can assume . We have also shown already that all vertices of are contained in . By construction, is a maximal subset of that is connected in . Since contains a vertex of , all of its vertices are contained in , so . Hence, .
Next, using (7), the average degree bound and the fact that is at most , we get that
(8) |
To finish the proof, plug (8) and then (7) into the definition of a polymer weight (Definition 14) and use the fact that for (See (1)) to obtain:
Remark 22.
Note that Lemma 21 crucially requires to be large enough for sufficient expansion and average degree properties to hold for all connected sets of size at least . While expansion properties hold for all (see e.g. [18]), we must treat sets as large as and for these we require large 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 large enough, whp over the following holds. For and any , it holds that
Proof.
Fix and let . If , then since is connected, , and the inequality is trivial. Thus, for the rest of the proof, assume that . Let and note that
For every ordered with , define . We claim that . Clearly, since all edges in are out-edges.
If is a singleton polymer, then neither of its endpoints are in small components of , thus setting its single edge to be in does not change the number of small components, so , and it follows that .
Hence, assume that is a non-singleton polymer with and consider the components of and . From Lemma 16, there is exactly one giant component in each of and . We claim that the components of are the giant component, together with the small components of that do not contain vertices of .
To prove the claim, first suppose is a small component of not containing vertices of . We use for the set of vertices of . Then no edge from is in , thus is a component of .
For the other direction, let be a small component of . The vertices of are in small components of , so by the definition of , . We wish to show that is a small component of that does not contain vertices of .
Suppose for contradiction that . Then, by the definition of non-singleton polymers, , resulting in , contradicting the fact that is a small component of . For the rest of the proof, we can therefore assume that .
To finish the proof of the claim, we wish to show that is a small component of . Since is a subgraph of , there is a non-empty subgraph of which is a component of . Suppose for contradiction that . Since is connected in , there exists an edge where and . But then must be an in-edge for but not for , hence . By the definition of non-singleton polymers, either or is in . Both and are in so we have contradicted , which we have already shown. Thus , which concludes the proof of the claim.
By the claim, is the number of small components of that contain vertices of . By the definition of polymers this is exactly , so by the definition of polymer weights .
For every , both and are in . Furthermore, and for any distinct , and are distinct. Thus
Hence we can write
which is .
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 such that for all large enough, for all sufficiently large reals , the following holds whp over for all real . For any ,
Proof.
By Proposition 10 and Lemma 21, there is a constant such that whp any connected vertex set with size at least has average degree at least , and any ordered polymer with has . Also whp the bound from Lemma 23 holds.
Let . By a union bound and Lemma 23 it is enough to show
Start by using the bound on the polymer weights from Lemma 21 to show that
Then note that any in this sum has hence by Proposition 10 it has average degree at least hence degree at least . Thus, the sum is at most
Now we bound the number of polymers of the given total degree . There are connected subgraphs of total degree in any graph (see e.g. [24, Lemma 6]). For any connected subset of total degree , there are at most edges incident to its vertices, thus there are at most polymers with (each of its edges can be either in or out). Thus the sum is at most
For all sufficiently large, , so the sum is . For sufficiently large, this is .
4 Fast convergence of the RC dynamics and proof of Theorem 1
In order to prove Theorem 1, we use the RC dynamics to obtain samples from the ordered and the disordered phases separately. For the sake of completeness, recall that a transition from to is done as follows:
-
(1)
Pick an edge uniformly at random
-
(2)
If is a cut edge of the graph , then with probability set . With all remaining probability set
-
(3)
Otherwise, with probability , set . With all remaining probability set .
Proving mixing of the RC dynamics 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 being an in-edge depends only on a small neighbourhood around , 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 be sufficiently large. Then, for all sufficiently large, whp over , for all and , the random cluster dynamics initialized from all-out satisfies for .
Theorem 26.
Let be sufficiently large. Then, for all sufficiently large, whp over , for all and , the random cluster dynamics initialized from all-in satisfies for
Proof of Theorem 1.
For and , it follows from Theorems 4, 25 and 26 that we can get an -sample by initializing the Glauber dynamics from all-out or all-in respectively.
Note that both theorems give mixing even for that depends on . We use this to obtain the an approximation for and hence mixing for . By considering a sequence of ’s we can approximate and within -factor using standard self-reducibility techniques (for more details see e.g. [13, 3]), and thus, by Theorem 4 get a approximation for . For , we then obtain an 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 . 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.