Pith. sign in

REVIEW 1 major objections 3 minor 45 references

Poisson trees mix nearly linearly under low-temperature Potts boundaries, and the result speeds up sampling on sparse random graphs to near-linear time at all temperatures.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

On Poisson trees with monochromatic boundary, low-temperature Potts Glauber dynamics mixes in |V(T)| n^{o(1)} steps, giving a near-linear-time all-temperature sampler for G(n,d/n).

T0 review reviewed 2026-08-03 challenge →

load-bearing objection Near-linear mixing on Poisson trees for low-temperature Potts — the missing irregular-tree analogue, powering an all-temperature n^{1+δ} sampler for G(n,d/n); solid work, but the pgf-tail-bound proof needs a presentational fix. the 1 major comments →

arxiv 2607.29495 v1 pith:XOTH7EI6 submitted 2026-07-31 math.PR cs.DM

Fast Mixing for Low-Temperature Potts Models via Poisson Trees

Zongchen Chen , Andreas Galanis , Leslie Ann Goldberg , Xandru Mifsud , Paulina Smolarova , Xusheng Zhang This is my paper
classification math.PR cs.DM MSC 60J1005C8082B2068W20
keywords Potts modelGlauber dynamicsmixing timePoisson Galton-Watson treerandom graph G(n,d/n)low-temperature regimenon-reconstructionrandom-cluster model
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that Glauber dynamics for the ferromagnetic Potts model on a Poisson Galton–Watson tree, with a monochromatic boundary condition at the leaves, mixes in time |V| n^{o(1)} for large average degree d and number of colours q, provided the inverse temperature beta exceeds (1+1.01/theta) log q / d. This is the first analogue for irregular tree neighbourhoods of the fast-mixing results previously known for regular trees. The consequence is algorithmic: approximate sampling from the q-state Potts model on the sparse random graph G(n,d/n) can be done in O(n^{1+delta}) time at every temperature, improving the previous n^{O(log q)} bound. The proof is carried by an adaptive block decomposition that handles the non-uniform effect of the monochromatic boundary in trees with fluctuating degrees and dead-end branches.

Core claim

The central claim is Theorem 2: for all large enough real d, all integer q >= d^theta, and all beta above the stated threshold, a Poisson tree truncated at depth h = floor(K log_d n) has, with probability 1 - n^{-kappa}, Glauber mixing time at most |V(T^h)| n^{o(1)} under the monochromatic boundary condition. The proof's engine is a block cover adapted to the tree's irregular structure: vertices are classified as h-good when their subtree contains a large regular subtree, and blocks are formed by stopping after roughly log log n good vertices on every root-to-leaf path. In dense good regions the boundary effect dies out quickly (non-reconstruction), while sparse regions are absorbed and cont

What carries the argument

The adaptive block cover of the Poisson tree. A vertex is h-good if its subtree contains a complete D-ary subtree of depth down to the boundary, with D approximately (1-eps)d. Each block B_v is the maximal subtree rooted at v whose root-to-leaf paths cross at most ell h-good vertices, with ell chosen about log log n. This structure does three jobs: it makes non-reconstruction decay rho = 2 W N p^{ell+1} small via the marginal bound on good vertices; it keeps block sizes and degree sums within the concentration bounds of Lemma 12; and it allows a centroid decomposition inside each block, so local mixing costs q^{O(log N)} e^{O(beta W)} = n^{o(1)} instead of the naive n^{O(beta)} bound from a

Load-bearing premise

Everything rests on the high-probability structural event of Lemma 12: in every block of the adaptive decomposition, the block has at most (6d)^ell (log n)^2 vertices, and every subset of at most log_2(2N) vertices has total degree at most C1 log n / log log n; if this concentration fails, the local mixing factor and non-reconstruction decay are no longer n^{o(1)} and the argument collapses.

What would settle it

Exhibit, on a Poisson tree of growing size n, a block in the adaptive decomposition containing a subset S of size at most log_2(2N) whose degree sum exceeds C1 log n / log log n with probability larger than n^{-kappa}; such a tree would violate the Lemma 12 event and break the local-mixing bound that the theorem requires.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Mixing time on Poisson trees with monochromatic boundary is near-linear, so the irregularity of random-tree neighbourhoods no longer forces polynomial losses in the mixing analysis.
  • Approximate sampling from the Potts distribution on G(n,d/n) runs in O(n^{1+delta}) time at every temperature, for any fixed delta > 0, when d is large and q is large enough.
  • The spectral gap and log-Sobolev constants of the Potts and random-cluster chains on these trees are at least 1/(|V| n^{o(1)}), essentially optimal up to n^{o(1)}.
  • The theorem covers the ordered low-temperature regime down to beta close to the uniqueness threshold log q / d when q is taken large relative to d.
  • The lifting result lets a Potts entropy-factorisation bound be converted into a random-cluster mixing bound on arbitrary graphs of bounded maximum degree, with only an O(q^3 e^{3 beta Delta}) overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The adaptive block method should transfer to other inhomogeneous random trees, such as neighbourhoods of sparse graphs with degree fluctuations or heavy tails, where regular-tree analyses fail.
  • The n^{o(1)} factor hides iterated logarithm terms; a plausible next step is to tighten the analysis to optimal O(n log n) or O(n) mixing on the low-temperature phase of G(n,d/n).
  • Because the final G(n,d/n) algorithm inherits a stronger q = d^{Omega(d)} lower bound from the polymer phase analysis, one could test whether the Poisson-tree bound alone supports sampling at q = d^{1+o(1)} if phase proportions are estimated by a different method.
  • The centroid-decomposition local mixing argument is independent of the Potts setting and could replace root-to-leaf comparison arguments in other tree-structured spin systems with large degree sums.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper proves that, for all large enough real d, all integer q ≥ d^θ, and all β > (1 + 1.01/θ) log(q)/d, the Glauber dynamics for the Potts model on a Poisson tree truncated at depth h = ⌊K log_d n⌋ with monochromatic boundary has mixing time at most |V(T^h)| n^{o(1)} with probability 1 - n^{-κ} over the tree. The proof introduces an adaptive block decomposition based on dense 'good' subtrees, combines a non-reconstruction property with local mixing via centroid decompositions, and lifts the entropy factorization to the random-cluster model. As an application, the paper gives a near-linear-time approximate sampler for the Potts model on G(n,d/n) at all temperatures, improving on the previous polynomial bound of Galanis–Goldberg–Smolarova.

Significance. If correct, this is a significant advance: it extends the classical regular-tree mixing results of Martinelli–Sinclair–Weitz and Blanca–Chen–Stefankovic–Vigoda to the irregular Poisson trees that arise as local neighbourhoods of sparse random graphs, and it yields a concrete algorithmic speedup. The proof is detailed and largely self-contained, with explicit lemmas, deferred proofs in appendices, and no post-hoc parameter fitting. The main technical engine, Theorem 2, is a new structural result about block non-reconstruction and local mixing on Poisson trees, and the Edwards–Sokal lifting to the random-cluster model is a useful general tool. However, the proof as written contains a load-bearing gap in the concentration argument for block sizes (Lemma 39 / Lemma 12), so the central claim is not yet fully supported.

major comments (1)
  1. [Appendix C.1, Lemma 39] The induction proving that f_ℓ(e^{θ/(6d)^ℓ}) is defined does not go through under the pgf domain stated in Lemma 37. Lemma 37 gives the domain of f as t ≤ ((e^{d p_bad}-1)/(d p_bad))^{1/D}. Since d p_bad = e^{-Ω(d)}, this right-hand side is 1+O(e^{-Ω(d)}) for large d. The inductive step requires e^{θ'} ≤ ((e^{d p_bad}-1)/(d p_bad))^{1/D} with θ'=θ/(6d), but e^{θ'}=1+Θ(1/d), which lies outside that domain. The accompanying bound e^{Dθ'} ≤ e^{1/6}<1 is also numerically false. Consequently Lemma 40 and the block-size bound in Lemma 12(i) are unsupported as written. The argument may be repairable by replacing 6d with a sufficiently large constant C(d) and correcting the Borel radius, but the current proof has a genuine gap at a load-bearing point.
minor comments (3)
  1. [Lemma 9 proof] In the display estimating the probability that a good vertex differs from the boundary colour, the denominator should be Z_+^v rather than Z_-^v; as written it reads 'Z_-^v / Z_-^v'.
  2. [Lemma 39] The inequality 'e^{1/6}<1' is false (e^{1/6}>1). If the intended Borel radius is the standard e^{d p_bad-1}/(d p_bad), then the proof still needs to state the correct comparison rather than this invalid bound.
  3. [Lemma 37] The notation '( edpbad −1 dpbad )' is ambiguous: it could be read as (e^{d p_bad}-1)/(d p_bad) or e^{d p_bad-1}/(d p_bad). The authors should disambiguate the formula, since the proof in Lemma 39 depends sensitively on the domain.

Circularity Check

0 steps flagged

No significant circularity: Theorem 2 is derived from stated structural lemmas; the only mild self-citation burden is [17] in the application, with independent published content.

full rationale

The central Poisson-tree mixing result (Theorem 2) is not circular. Its proof constructs an adaptive block cover from h-good vertices, then verifies the three hypotheses of Theorem 5: cover radius R*≤h is immediate, non-reconstruction follows from Lemma 9 applied along the ℓ+1 good vertices on each path to ∂B_v, and local mixing follows from Lemmas 11 and 12. Theorem 5 itself is proved in Section 3 via variance factorization (Lemmas 16 and 17), and the passage to log-Sobolev and mixing time uses Lemmas 7 and 6. None of these statements defines an input in terms of the claimed output, and no constant is fitted to force the n^{o(1)} factor. The paper cites [10] and [17] by overlapping authors, but [10] is only an inspiration for non-uniform decompositions and is not used as the proof of any lemma here; [17] supplies the phase decomposition and weak spatial mixing used for the algorithmic application, and is a published prior work with independent content, so this is normal incremental self-citation rather than circularity. I also note a correctness concern that is not a circularity: in Lemma 39 the induction requires e^{θ'} ≤ ((e^{d p_bad}-1)/(d p_bad))^{1/D} with θ'=θ/(6d); for large d the right-hand side is 1+o(1/d) while e^{θ'}=1+Θ(1/d), and the accompanying claim 'e^{Dθ'} = e^{θD/(6d)} ≤ e^{1/6} <1' is numerically false since the left side exceeds 1. This appears to leave Lemma 12(i) unsupported as written, but it is an internal proof gap, not a reduction of the conclusion to its assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

No parameters are fitted to data; the theorem quantifies 'large enough d' and 'sufficiently large q'. Auxiliary constants such as epsilon, delta, xi, C0, and C1 are chosen within open ranges to satisfy inequalities and are not input constants of the result. The main extra-mathematical assumptions are the standard Markov-chain comparison tools and the prior [17] phase decomposition, which is cited rather than re-derived.

axioms (6)
  • standard math Standard comparison facts linking spectral gap, log-Sobolev constant, and Glauber mixing time (Lemma 6, Lemma 45; [36,40]).
    Invoked in Theorem 5, Lemma 7, Lemma 13 and the proof of Theorem 1 to convert spectral/log-Sobolev bounds into mixing-time and running-time bounds.
  • standard math Edwards-Sokal coupling between Potts and random-cluster measures, and factorization of entropy over product spaces (Section 3.2, Lemma 18).
    Used to lift the Potts entropy-factorization bound on Poisson trees to the all-wired random-cluster dynamics on the same tree.
  • domain assumption Poisson Galton-Watson trees correctly approximate the local BFS structure of G(n,d/n), including coupling with parameter d+d^2/n and bounded cycle counts (Lemma 14 and [5, Lemma 2.2]).
    This is what connects the abstract Poisson-tree mixing result to the actual random graph; if the coupling failed, Lemma 15 and Theorem 1 would not follow.
  • domain assumption The phase decomposition and weak spatial mixing within the ordered phase for q >= d^{Omega(d)} on the giant component of G(n,d/n) (Theorem 26 of [17]).
    Load-bearing for Theorem 1: it lets the algorithm treat the random-cluster distribution as a mixture of ordered/disordered phases and controls the intermediate temperature regime.
  • standard math Existence of centroids in trees, with deletion halving every component (used in Lemma 11's centroid-decomposition proof; [26]).
    The centroid decomposition is what reduces the local block mixing bound to q^{O(log N)} e^{O(beta W)} instead of an n^{O(1)} depth-dependent bound.
  • domain assumption Lemma 9's quantitative regime: D(1-delta) >= xi and q^{1-xi} <= delta xi / (2(1-delta)D) log q, satisfied for large d when q >= d^theta and xi > 1+1/theta.
    This parameter regime forces the exponential decay of the probability that a good vertex disagrees with the boundary color, which is the key to non-reconstruction along blocks.

reviewed 2026-08-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Mixing for Low-Temperature Potts Models via Poisson Trees." pith.science (2026). https://pith.science/paper/XOTH7EI6

@misc{pith2026260729495,
  author       = {Pith},
  title        = {Pith review of: Fast Mixing for Low-Temperature Potts Models via Poisson Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XOTH7EI6}},
  note         = {Machine review of arXiv:2607.29495}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The $q$-state ferromagnetic Potts model on a graph $G$ is a probability distribution on all $q$-colourings of $G$ that favours many monochromatic edges. Approximate sampling from the Potts model is a central problem in the study of spin systems on sparse graphs, especially in the low-temperature regime, where the model strongly favours ordered configurations, often creating bottlenecks that make Markov-chain sampling inefficient or difficult to analyse. We focus on the sparse random graph $G(n,d/n)$. The local neighbourhoods of $G(n,d/n)$ are tree-like, but the relevant underlying graph is a Poisson Galton-Watson tree. This motivates the study of Glauber dynamics for the low-temperature Potts model on such trees with monochromatic boundary conditions. The Poisson setting introduces difficulties absent from the regular case: degrees fluctuate, long induced paths may appear, and branches can terminate before reaching the boundary. As a result, the effect of the monochromatic boundary at the leaves is much less uniform. Our main result shows near-linear mixing for the Glauber dynamics on Poisson trees with monochromatic boundary conditions. This extends the corresponding regular-tree results of Martinelli, Sinclair, and Weitz (SODA 2004) and of Blanca, Chen, Stefankovi\v{c}, and Vigoda (RANDOM 2021) to the irregular trees arising from sparse random graphs. Our proof introduces an adaptive block decomposition of the tree, built around regions containing large regular subtrees, and combines it with correlation-decay estimates and functional-inequality arguments. We also obtain a near-linear-time approximate sampling algorithm for the Potts model on $G(n,d/n)$ at all temperatures, speeding up the best previous algorithm of Galanis, Goldberg, and Smolarova (ICALP 2025). The main new ingredient is a refined analysis of the low-temperature regime, building on the Poisson tree result.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 3 linked inside Pith

  1. [1]

    Fast sampling via spectral independence beyond bounded-degree graphs.ACM Transactions on Algorithms, 20(1):1–26, 2024

    Ivona Bez ´akov´a, Andreas Galanis, Leslie Ann Goldberg, and Daniel ˇStefankoviˇc. Fast sampling via spectral independence beyond bounded-degree graphs.ACM Transactions on Algorithms, 20(1):1–26, 2024

    2024

  2. [2]

    Entropy decay in the Swendsen–Wang dynamics onZ d

    Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda. Entropy decay in the Swendsen–Wang dynamics onZ d. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1551–1564, 2021

    2021

  3. [3]

    The Swendsen–Wang dynamics on trees.Random Structures & Algorithms, 62(4):791–831, 2023

    Antonio Blanca, Zongchen Chen, Daniel ˇStefankoviˇc, and Eric Vigoda. The Swendsen–Wang dynamics on trees.Random Structures & Algorithms, 62(4):791–831, 2023

    2023

  4. [4]

    On the tractability of sampling from the Potts model at low temperatures via Swendsen-Wang dynamics.CoRR, abs/2304.03182, 2023.arXiv:2304

    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.arXiv:2304. 03182

    Pith/arXiv arXiv 2023

  5. [5]

    Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics.The Annals of Applied Probability, 33(6B):4997–5049, 2023

    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. 16

    2023

  6. [6]

    On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics.Probability Theory and Related Fields, 191:1121– 1168, 2024

    Antonio Blanca and Reza Gheissari. On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics.Probability Theory and Related Fields, 191:1121– 1168, 2024. Extended abstract appeared in FOCS 2023

    2024

  7. [7]

    Uniqueness and mixing in the low-temperature random-cluster model on trees and random graphs, 2026

    Antonio Blanca, Reza Gheissari, Heehyun Park, and Xusheng Zhang. Uniqueness and mixing in the low-temperature random-cluster model on trees and random graphs, 2026. arXiv:2604.20693

    Pith/arXiv arXiv 2026

  8. [8]

    Block factorization of the relative entropy via spatial mixing

    Pietro Caputo and Daniel Parisi. Block factorization of the relative entropy via spatial mixing. Communications in Mathematical Physics, 388:793–818, 2021

    2021

  9. [9]

    Algorithms for the ferromagnetic Potts model on expanders.Combinatorics, Proba- bility and Computing, 33(4):487–517, 2024

    Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, and Cor- rine Yap. Algorithms for the ferromagnetic Potts model on expanders.Combinatorics, Proba- bility and Computing, 33(4):487–517, 2024

    2024

  10. [10]

    Combinatorial approach for factorization of variance and entropy in spin systems

    Zongchen Chen. Combinatorial approach for factorization of variance and entropy in spin systems. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4988–5012, 2024

    2024

  11. [11]

    Fast algorithms at low temperatures via Markov chains.Random Structures & Algo- rithms, 58(2):294–321, 2021

    Zongchen Chen, Andreas Galanis, Leslie A Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via Markov chains.Random Structures & Algo- rithms, 58(2):294–321, 2021

    2021

  12. [12]

    Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1537–1550, 2021

    2021

  13. [13]

    Metastability of the Potts ferromagnet on random reg- ular graphs.Communications in Mathematical Physics, 2023

    Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, and Eric Vigoda. Metastability of the Potts ferromagnet on random reg- ular graphs.Communications in Mathematical Physics, 2023

    2023

  14. [14]

    Statistical physics approaches to Unique Games

    Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical physics approaches to Unique Games. InProceedings of the 35th Computational Complexity Conference, CCC ’20, 2020

    2020

  15. [15]

    On the mixing time of Glauber dynamics for the hard-core and related models onG(n, d/n)

    Charilaos Efthymiou and Weiming Feng. On the mixing time of Glauber dynamics for the hard-core and related models onG(n, d/n). In50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261, pages 54:1–54:17, 2023

    2023

  16. [16]

    Hayes, Daniel ˇStefankoviˇc, and Eric Vigoda

    Charilaos Efthymiou, Thomas P. Hayes, Daniel ˇStefankoviˇc, and Eric Vigoda. Sampling random colorings of sparse random graphs. InProceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1759–1771, 2018

    2018

  17. [17]

    Low-temperature sampling on sparse random graphs

    Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Low-temperature sampling on sparse random graphs. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 83–1, 2025

    2025

  18. [18]

    Sampling from the random clus- ter model on random regular graphs at all temperatures via Glauber dynamics.Combinatorics, Probability and Computing, 34(3):359–391, 2025

    Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Sampling from the random clus- ter model on random regular graphs at all temperatures via Glauber dynamics.Combinatorics, Probability and Computing, 34(3):359–391, 2025. Extended abstract appeared in RANDOM 2023. 17

    2025

  19. [19]

    Planting and MCMC Sampling from the Potts Model

    Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Planting and MCMC Sampling from the Potts Model. In43rd International Symposium on Theoretical Aspects of Computer Sci- ence (STACS 2026), volume 364 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 39:1–39:19, 2026

    2026

  20. [20]

    Fast algorithms for general spin systems on bipartite expanders.ACM Transactions on Computation Theory (TOCT), 13(4):1– 18, 2021

    Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast algorithms for general spin systems on bipartite expanders.ACM Transactions on Computation Theory (TOCT), 13(4):1– 18, 2021

    2021

  21. [21]

    Ferromagnetic Potts model: Refined #BIS-hardness and related results.SIAM Journal on Computing, 45(6):2004–2065, 2016

    Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts model: Refined #BIS-hardness and related results.SIAM Journal on Computing, 45(6):2004–2065, 2016

    2004

  22. [22]

    Low-temperature Ising dynamics with random initializa- tions.Proceedings of the Annual ACM Symposium on Theory of Computing, pages 1445–1458, 2022

    Reza Gheissari and Alistair Sinclair. Low-temperature Ising dynamics with random initializa- tions.Proceedings of the Annual ACM Symposium on Theory of Computing, pages 1445–1458, 2022

    2022

  23. [23]

    Spatial mixing and the random-cluster dynamics on lattices

    Reza Gheissari and Alistair Sinclair. Spatial mixing and the random-cluster dynamics on lattices. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms,(SODA ’23) , pages 4606–4621, 2023

    2023

  24. [24]

    Approximating the partition function of the ferromag- netic Potts model.Journal of the ACM, 59(5):1–31, 2012

    Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromag- netic Potts model.Journal of the ACM, 59(5):1–31, 2012

    2012

  25. [25]

    Random cluster dynamics for the Ising model is rapidly mixing

    Heng Guo and Mark Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. The Annals of Applied Probability, 28(2):1292–1313, 2018

    2018

  26. [26]

    Addison-Wesley, Reading, MA, 1969

    Frank Harary.Graph Theory. Addison-Wesley, Reading, MA, 1969

    1969

  27. [27]

    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 Poincar´e, Probabilit´es et Statistiques, 59(2):817 – 848, 2023

    2023

  28. [28]

    Algorithmic Pirogov-Sinai theory

    Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1009–1020, 2019

    2019

  29. [29]

    Cambridge Series in Statisti- cal and Probabilistic Mathematics

    Remco van der Hofstad.Random Graphs and Complex Networks. Cambridge Series in Statisti- cal and Probabilistic Mathematics. Cambridge University Press, 2016

    2016

  30. [30]

    Fully Dy- namic Connectivity in $O(\log n(\log\log n)ˆ2)$ Amortized Expected Time.TheoretiCS, V ol- ume 2, 2023

    Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Fully Dy- namic Connectivity in $O(\log n(\log\log n)ˆ2)$ Amortized Expected Time.TheoretiCS, V ol- ume 2, 2023

    2023

  31. [31]

    John Wiley & Sons, Inc., 2000 - 2000

    Svante Janson, Tomasz Łuczak, and Andrzej Ruci ´nski.Random graphs. John Wiley & Sons, Inc., 2000 - 2000

    2000

  32. [32]

    Algorithms for #BIS-hard problems on expander graphs.SIAM Journal on Computing, 49(4):681–710, 2020

    Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs.SIAM Journal on Computing, 49(4):681–710, 2020

    2020

  33. [33]

    Polynomial-time approximation algorithms for the Ising model.SIAM Journal on Computing, 22(5):1087–1116, 1993

    Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model.SIAM Journal on Computing, 22(5):1087–1116, 1993. 18

    1993

  34. [34]

    Fast mixing in sparse random Ising models

    Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X Wu. Fast mixing in sparse random Ising models. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 120–128, 2024

    2024

  35. [35]

    Cambridge Series in Statistical and Probabilistic Mathematics

    Russell Lyons and Yuval Peres.Branching Processes, Second Moments, and Percolation, pages 131–173. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017

    2017

  36. [36]

    Lectures on glauber dynamics for discrete spin models

    Fabio Martinelli. Lectures on glauber dynamics for discrete spin models. In Pierre Bernard, editor,Lectures on Probability Theory and Statistics: Ecole d’Et ´e de Probailit´es de Saint-Flour XXVII - 1997, pages 93–191. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999

    1997

  37. [37]

    Fast mixing for independent sets, colorings and other models on trees

    Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Fast mixing for independent sets, colorings and other models on trees. InProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, pages 456––465, 2004

    2004

  38. [38]

    Glauber dynamics on trees: Boundary con- ditions and mixing time.Communications in Mathematical Physics, 250(2):301–334, 2004

    Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Glauber dynamics on trees: Boundary con- ditions and mixing time.Communications in Mathematical Physics, 250(2):301–334, 2004

    2004

  39. [39]

    Rapid mixing of Gibbs sampling on graphs that are sparse on average.Random Structures & Algorithms, 35(2):250–270, 2009

    Elchanan Mossel and Allan Sly. Rapid mixing of Gibbs sampling on graphs that are sparse on average.Random Structures & Algorithms, 35(2):250–270, 2009

    2009

  40. [40]

    Lectures on finite Markov chains

    Laurent Saloff-Coste. Lectures on finite Markov chains. In Pierre Bernard, editor,Lectures on Probability Theory and Statistics: Ecole d’Et´e de Probabilit´es de Saint-Flour XXVI-1996, pages 301–413. 1997

    1996

  41. [41]

    Rapid mixing of Swendsen–Wang dynamics in two dimensions

    Mario Ullrich. Rapid mixing of Swendsen–Wang dynamics in two dimensions. arXiv:1212.4908, 2012

    Pith/arXiv arXiv 2012

  42. [42]

    Comparison of Swendsen–Wang and heat-bath dynamics.Random Structures & Algorithms, 42(4):520–535, 2013

    Mario Ullrich. Comparison of Swendsen–Wang and heat-bath dynamics.Random Structures & Algorithms, 42(4):520–535, 2013. A The RC dynamics The RC dynamics is an analogue of the Potts Glauber dynamics: the states are the subsets ofE. The transition fromX t toX t+1 is done as follows:

    2013

  43. [43]

    Pick a uniformly random edgee∈E

  44. [44]

    Ifeis a cut-edge in(V, X t ∪ {e}), thenXt+1 =X t ∪ {e}with probabilityˆp:= eβ −1 q+eβ −1, and Xt+1 =X t \ {e}otherwise

  45. [45]

    downward

    Ifeis not a cut-edge in(V, X t ∪ {e}), thenXt+1 =X t ∪ {e}with probabilityp := 1−e −β, andX t+1 =X t \ {e}otherwise. We note that each step of the chain can be run in amortised timeO((logn) 2), see, e.g., [30]. B Remaining Proofs for Mixing Recall, for a graphGrooted at a vertexv,G ′ denotes the graph obtained fromGby deletingv. 19 B.1 Proof of Lemma 16 W...

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.