pith. sign in

arxiv: 2604.10525 · v2 · submitted 2026-04-12 · 💻 cs.DS · math.PR

Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics

Xiaoyu Chen , Zhe Ju , Tianshun Miao , Yitong Yin , Xinyuan Zhang This is my paper

Pith reviewed 2026-05-10 16:04 UTC · model grok-4.3

classification 💻 cs.DS math.PR
keywords Glauber dynamicsSwendsen-Wang dynamicsmixing timetwo-spin systemsIsing modeluniqueness thresholdlocalization schemesspectral gap
0
0 comments X p. Extension

The pith

Glauber dynamics mixes in polynomial time for antiferromagnetic two-spin systems exactly at the uniqueness threshold on trees.

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

This paper shows that the standard Glauber dynamics mixes in polynomial time for Gibbs distributions of antiferromagnetic two-spin systems at the critical threshold where the infinite regular tree measure loses uniqueness. This fills the remaining gap in the phase diagram for approximate sampling: polynomial-time mixing holds throughout the uniqueness regime including its boundary, while hardness holds outside it. The work also establishes that Swendsen-Wang dynamics achieves an optimal O(log n) mixing time together with a constant spectral gap for the ferromagnetic Ising model with external field on any bounded-degree graph. The proofs rest on a new family of localization schemes that tilt edge weights in a controlled way while preserving external fields.

Core claim

We prove that the Glauber dynamics mixes in polynomial time for the Gibbs distributions of antiferromagnetic two-spin systems at the critical threshold of the uniqueness phase transition of the Gibbs measure on infinite regular trees. We also prove an optimal O(log n) mixing time bound as well as an optimal Ω(1) spectral gap for the Swendsen-Wang dynamics for the ferromagnetic Ising model with an external field on bounded-degree graphs. These results are obtained via a new family of localization schemes that tilt general edge weights rather than vertex fields and that subsume Swendsen-Wang as a special case.

What carries the argument

Edge-tilting localization schemes, which extend prior field dynamics by modifying interaction weights on edges or hyperedges while preserving external fields and subsuming Swendsen-Wang dynamics.

If this is right

  • Approximate sampling from antiferromagnetic two-spin systems is in polynomial time throughout the uniqueness regime including the critical threshold.
  • Swendsen-Wang dynamics has optimal rapid mixing and constant spectral gap for Ising models with external fields on all bounded-degree graphs.
  • The edge-tilting framework enables mixing analysis for global chains beyond previous stochastic or vertex-field localization methods.
  • The computational phase transition for two-spin systems is now fully resolved between uniqueness and non-uniqueness regimes.

Where Pith is reading between the lines

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

  • The same edge-tilting approach may extend to analyze mixing times in models with hyperedges or in systems that combine both antiferromagnetic and ferromagnetic interactions.
  • Optimal mixing bounds for Swendsen-Wang could motivate its use in practical sampling algorithms when external fields are present.
  • If the localization preserves its properties on non-tree graphs, it might connect tree-based uniqueness thresholds to mixing on lattices with cycles.
  • The framework's ability to control bias while tilting interactions suggests broader applicability to other Markov chains used in statistical physics.

Load-bearing premise

The new edge-tilting localization schemes must extend the prior field dynamics without introducing uncontrolled bias when applied to bounded-degree graphs and trees.

What would settle it

An explicit large finite tree together with an antiferromagnetic two-spin parameter at the critical uniqueness value for which the Glauber mixing time is superpolynomial.

Figures

Figures reproduced from arXiv: 2604.10525 by Tianshun Miao, Xiaoyu Chen, Xinyuan Zhang, Yitong Yin, Zhe Ju.

Figure 1
Figure 1. Figure 1: Illustration of uniqueness regime for the Ising model ( [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
read the original abstract

We prove two results on the mixing times of Markov chains for two-spin systems. First, we show that the Glauber dynamics mixes in polynomial time for the Gibbs distributions of antiferromagnetic two-spin systems at the critical threshold of the uniqueness phase transition of the Gibbs measure on infinite regular trees. This completes the computational phase transition picture for antiferromagnetic two-spin systems, which includes near-linear-time optimal mixing in the uniqueness regime [Chen--Liu--Vigoda, STOC '21; Chen--Feng--Yin--Zhang, FOCS '22], NP-hardness of approximate sampling in the non-uniqueness regime [Sly--Sun, FOCS '12], and polynomial-time mixing at criticality (this work). Second, we prove an optimal $O(\log n)$ mixing time bound as well as an optimal $\Omega(1)$ spectral gap for the Swendsen--Wang dynamics for the ferromagnetic Ising model with an external field on bounded-degree graphs. To the best of our knowledge, these are the first sharp bounds on the mixing rate of this classical global Markov chain beyond mean-field or strong spatial mixing (SSM) regimes, and resolve a conjecture of [Feng--Guo--Wang, IANDC '23]. A key ingredient in both proofs is a new family of localization schemes that extends the field dynamics of [Chen--Feng--Yin--Zhang, FOCS '21] by tilting general edge (or hyperedge) weights rather than vertex fields. This framework, which subsumes the classical Swendsen--Wang dynamics as a special case, extends the localization framework of [Chen--Eldan, FOCS '22] beyond stochastic and field localizations, and enables controlled tilting of interaction strengths while preserving external fields.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves two results on mixing times for Markov chains on two-spin systems. First, Glauber dynamics mixes in polynomial time for antiferromagnetic two-spin Gibbs distributions at the uniqueness threshold on infinite regular trees, completing the phase-transition picture alongside prior uniqueness-regime near-linear mixing and non-uniqueness hardness results. Second, Swendsen-Wang dynamics has optimal O(log n) mixing time and Ω(1) spectral gap for the ferromagnetic Ising model with external field on bounded-degree graphs, resolving a conjecture. Both proofs rely on a new family of edge- (or hyperedge-) tilting localization schemes that generalize prior field dynamics, preserve external fields, and subsume Swendsen-Wang as a special case.

Significance. If the localization framework is shown to satisfy the required marginal-preservation and n-independent bias properties, the results would be significant: they close the last open case in the computational complexity of approximate sampling for antiferromagnetic two-spin systems and supply the first sharp mixing bounds for Swendsen-Wang dynamics outside mean-field or strong-spatial-mixing regimes. The new tilting schemes extend the localization toolkit of Chen-Eldan and Chen-Feng-Yin-Zhang and could apply to other global chains.

major comments (1)
  1. [Localization framework section (and comparison lemmas)] The two headline theorems both depend on the edge-tilting localization schemes (introduced to extend field dynamics) satisfying three load-bearing properties: exact reduction to prior field dynamics on uniform edges, preservation of external fields, and total-variation distance to the original measure bounded by a factor independent of n and maximum degree. Without an explicit verification of these properties (including the resulting comparison lemmas) on trees and bounded-degree graphs at the uniqueness threshold, the transfer of polynomial / O(log n) mixing bounds from the localized chains to the original Glauber and Swendsen-Wang chains does not go through.
minor comments (1)
  1. The abstract is information-dense; splitting the two results into separate paragraphs would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the positive assessment of the significance of our results. We address the major comment below.

read point-by-point responses

  1. Referee: [Localization framework section (and comparison lemmas)] The two headline theorems both depend on the edge-tilting localization schemes (introduced to extend field dynamics) satisfying three load-bearing properties: exact reduction to prior field dynamics on uniform edges, preservation of external fields, and total-variation distance to the original measure bounded by a factor independent of n and maximum degree. Without an explicit verification of these properties (including the resulting comparison lemmas) on trees and bounded-degree graphs at the uniqueness threshold, the transfer of polynomial / O(log n) mixing bounds from the localized chains to the original Glauber and Swendsen-Wang chains does not go through.

    Authors: We thank the referee for highlighting the need for clear verification of the load-bearing properties of the edge-tilting schemes. These properties are established in the localization framework section: the exact reduction to prior field dynamics is shown when restricting to uniform edges, external fields are preserved by construction of the tilting operator, and the total-variation bound independent of n and maximum degree follows from the bounded-degree assumption together with the uniqueness threshold condition on the tree. The comparison lemmas transferring the mixing bounds from the localized chains to Glauber dynamics (on trees) and to Swendsen-Wang dynamics (on bounded-degree graphs) are derived directly from these properties in the subsequent sections. To make the logical flow more transparent, we will add a short dedicated subsection that explicitly lists and cross-references the three properties along with the resulting comparison statements. revision: partial

Circularity Check

0 steps flagged

New edge-tilting localization extends prior field dynamics via explicit construction; mixing bounds derive from comparison lemmas rather than self-referential inputs.

full rationale

The derivation introduces a new family of localization schemes that tilt edge weights while preserving external fields and subsuming Swendsen-Wang as a special case. This extends the field dynamics of Chen-Feng-Yin-Zhang (FOCS '21) and the localization framework of Chen-Eldan (FOCS '22) by explicit generalization rather than by redefining inputs in terms of outputs. The polynomial mixing claim at the antiferromagnetic uniqueness threshold and the O(log n) SW bounds rely on comparison lemmas transferring from the localized chain, which are not shown to collapse to fitted parameters or prior self-citations by construction. Self-citations to overlapping-author works (Chen-Liu-Vigoda, Chen-Feng-Yin-Zhang) support the uniqueness regime and field dynamics but are not load-bearing for the new tilting mechanism or the claimed times; the phase-transition completion cites external hardness results (Sly-Sun). No self-definitional, fitted-prediction, or ansatz-smuggling reductions appear.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work rests on standard Markov-chain theory and known phase-transition facts for two-spin systems on trees; the main addition is the new localization method rather than new axioms or fitted constants.

axioms (2)
  • standard math Standard definitions and properties of mixing time and spectral gap for reversible Markov chains
    Invoked to state the O(log n) mixing and Ω(1) gap claims.
  • domain assumption Existence of a uniqueness/non-uniqueness phase transition threshold for antiferromagnetic two-spin systems on infinite regular trees
    Central to identifying the critical threshold where the new mixing result applies.
invented entities (1)
  • Edge-tilting localization schemes no independent evidence
    purpose: Extend field dynamics to tilt general edge weights while preserving external fields and subsuming Swendsen-Wang
    New technical framework introduced to prove both mixing results.

pith-pipeline@v0.9.0 · 5643 in / 1548 out tokens · 63165 ms · 2026-05-10T16:04:06.712361+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Glauber dynamics for random field Ising models on bounded degree graphs and MLSI

    math.PR 2026-05 unverdicted novelty 7.0

    Glauber dynamics for RFIM on bounded-degree graphs mixes in polynomial time w.h.p. under anti-concentrated random fields, with MLSI and weak Poincaré inequalities also established.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · cited by 1 Pith paper

  1. [1]

    Entropic independence I : Modified log- S obolev inequalities for fractionally log-concave distributions and high-temperature I sing models

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence I : Modified log- S obolev inequalities for fractionally log-concave distributions and high-temperature I sing models. arXiv preprint arXiv:2106.04105 , 2021

    work page arXiv 2021

  2. [2]

    Entropic independence: optimal mixing of down-up random walks

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy - Duong Vuong. Entropic independence: optimal mixing of down-up random walks. In STOC , pages 1418--1430, 2022

    work page 2022

  3. [3]

    Improved analysis of higher order random walks and applications

    Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In STOC , pages 1198--1211, 2020

    work page 2020

  4. [4]

    Spectral independence in high-dimensional expanders and applications to the hardcore model

    Nima Anari, Kuikui Liu, and Shayan Oveis Gharan . Spectral independence in high-dimensional expanders and applications to the hardcore model. In FOCS , pages 1319--1330. 2020

    work page 2020

  5. [5]

    Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan , and Cynthia Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In STOC , pages 1--12, 2019

    work page 2019

  6. [6]

    On mixing of M arkov chains: Coupling, spectral independence, and entropy factorization

    Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, and Eric Vigoda. On mixing of M arkov chains: Coupling, spectral independence, and entropy factorization. In SODA , pages 3670--3692, 2022

    work page 2022

  7. [7]

    Entropy decay in the S wendsen- W ang dynamics on Z^d

    Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda. Entropy decay in the S wendsen- W ang dynamics on Z^d . Ann. Appl. Probab. , 32(2):1018--1057, 2022

    work page 2022

  8. [8]

    Log- S obolev inequality for near critical I sing models

    Roland Bauerschmidt and Benoit Dagallier. Log- S obolev inequality for near critical I sing models. Comm. Pure Appl. Math. , 77(4):2568--2576, 2024

    work page 2024

  9. [9]

    Rapid mixing on random regular graphs beyond uniqueness

    Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing on random regular graphs beyond uniqueness. In FOCS , pages 2170--2193, 2025

    work page 2025

  10. [10]

    Rapid mixing at the uniqueness threshold

    Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing at the uniqueness threshold. In STOC , pages 879--–890, 2025

    work page 2025

  11. [11]

    Localization schemes: A framework for proving mixing bounds for M arkov chains (extended abstract)

    Yuansi Chen and Ronen Eldan. Localization schemes: A framework for proving mixing bounds for M arkov chains (extended abstract). In FOCS , pages 110--122, 2022

    work page 2022

  12. [12]

    Rapid mixing via coupling independence for spin systems with unbounded degree

    Xiaoyu Chen and Weiming Feng. Rapid mixing via coupling independence for spin systems with unbounded degree. In Approximation, randomization, and combinatorial optimization. A lgorithms and techniques , volume 353 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 68, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2025

    work page 2025

  13. [13]

    Rapid mixing of G lauber dynamics via spectral independence for all degrees

    Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of G lauber dynamics via spectral independence for all degrees. In FOCS , pages 137--148, 2021

    work page 2021

  14. [14]

    Optimal mixing for two-state anti-ferromagnetic spin systems

    Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Optimal mixing for two-state anti-ferromagnetic spin systems. In FOCS , pages 588--599, 2022

    work page 2022

  15. [15]

    Improved mixing of critical hardcore model

    Zongchen Chen and Tianhui Jiang. Improved mixing of critical hardcore model. In Alina Ene and Eshan Chattopadhyay, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , volume 353 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 51:1--51:22, Dagstuhl, Germany, 2025. Schl...

    work page 2025

  16. [16]

    Rapid mixing of G lauber dynamics up to uniqueness via contraction

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of G lauber dynamics up to uniqueness via contraction. In FOCS , pages 1307--1318. IEEE Computer Soc., Los Alamitos, CA, [2020] 2020

    work page 2020

  17. [17]

    Optimal mixing of G lauber dynamics: entropy factorization via high-dimensional expansion

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of G lauber dynamics: entropy factorization via high-dimensional expansion. In STOC , pages 1537--1550, 2021

    work page 2021

  18. [18]

    Rapid mixing of glauber dynamics up to uniqueness via contraction

    Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of glauber dynamics up to uniqueness via contraction. SIAM J. Comput. , 52(1):196--237, 2023

    work page 2023

  19. [19]

    Spectral independence beyond total influence on trees and related graphs

    Xiaoyu Chen, Xiongxin Yang, Yitong Yin, and Xinyuan Zhang. Spectral independence beyond total influence on trees and related graphs. In SODA , pages 5388--5417, 2025

    work page 2025

  20. [20]

    A near-linear time sampler for the I sing model with external field

    Xiaoyu Chen and Xinyuan Zhang. A near-linear time sampler for the I sing model with external field. In SODA , pages 4478--4503, 2023

    work page 2023

  21. [21]

    On counting independent sets in sparse graphs

    Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM J. Comput. , 31(5):1527--1541, 2002

    work page 2002

  22. [22]

    The mixing time evolution of G lauber dynamics for the mean-field I sing model

    Jian Ding, Eyal Lubetzky, and Yuval Peres. The mixing time evolution of G lauber dynamics for the mean-field I sing model. Comm. Math. Phys. , 289(2):725--764, 2009

    work page 2009

  23. [23]

    Mixing time of critical I sing model on trees is polynomial in the height

    Jian Ding, Eyal Lubetzky, and Yuval Peres. Mixing time of critical I sing model on trees is polynomial in the height. Comm. Math. Phys. , 295(1):161--207, 2010

    work page 2010

  24. [24]

    On regular hypergraphs of high girth

    David Ellis and Nathan Linial. On regular hypergraphs of high girth. Electron. J. Combin. , 21(1):Paper 1.54, 17, 2014

    work page 2014

  25. [25]

    Thin shell implies spectral gap up to polylog via a stochastic localization scheme

    Ronen Eldan. Thin shell implies spectral gap up to polylog via a stochastic localization scheme. Geometric and Functional Analysis , 23(2):532--569, 2013

    work page 2013

  26. [26]

    Swendsen- W ang dynamics for the ferromagnetic I sing model with external fields

    Weiming Feng, Heng Guo, and Jiaheng Wang. Swendsen- W ang dynamics for the ferromagnetic I sing model with external fields. Inform. and Comput. , 294:Paper No. 105066, 34, 2023

    work page 2023

  27. [27]

    Random cluster dynamics for the I sing model is rapidly mixing

    Heng Guo and Mark Jerrum. Random cluster dynamics for the I sing model is rapidly mixing. Ann. Appl. Probab. , 28(2):1292--1313, 2018

    work page 2018

  28. [28]

    The computational complexity of two-state spin systems

    Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random Structures Algorithms , 23(2):133--154, 2003

    work page 2003

  29. [29]

    Reconstruction for models on random graphs

    Antoine Gerschenfeld and Andrea Montanari. Reconstruction for models on random graphs. In FOCS , pages 194--204, 2007

    work page 2007

  30. [30]

    Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region

    Andreas Galanis, Daniel S tefankovi c , and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM , 62(6):Art. 50, 60, 2015

    work page 2015

  31. [31]

    Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models

    Andreas Galanis, Daniel S tefankovi c , and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing , 25(04):500--559, 2016

    work page 2016

  32. [32]

    Glauber dynamics for the mean-field ising model: cut-off, critical power law, and metastability

    David A Levin, Malwina J Luczak, and Yuval Peres. Glauber dynamics for the mean-field ising model: cut-off, critical power law, and metastability. Probability Theory and Related Fields , 146(1):223, 2010

    work page 2010

  33. [33]

    Approximate counting via correlation decay in spin systems

    Liang Li, Pinyan Lu, and Yitong Yin. Approximate counting via correlation decay in spin systems. In SDOA , pages 922--940, 2012

    work page 2012

  34. [34]

    Correlation decay up to uniqueness in spin systems

    Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In SODA , pages 67--84, 2013

    work page 2013

  35. [35]

    A power law of order 1/4 for critical mean field S wendsen- W ang dynamics

    Yun Long, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean field S wendsen- W ang dynamics. Mem. Amer. Math. Soc. , 232(1092):vi+84, 2014

    work page 2014

  36. [36]

    Critical I sing on the square lattice mixes in polynomial time

    Eyal Lubetzky and Allan Sly. Critical I sing on the square lattice mixes in polynomial time. Comm. Math. Phys. , 313(3):815--836, 2012

    work page 2012

  37. [37]

    On the hardness of sampling independent sets beyond the tree threshold

    Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Related Fields , 143(3-4):401--439, 2009

    work page 2009

  38. [38]

    Polynomial mixing of the critical G lauber dynamics for the I sing model

    Kyprianos-Iason Prodromidis and Allan Sly. Polynomial mixing of the critical G lauber dynamics for the I sing model. arXiv preprint arXiv:2411.10318 , 2024

    work page arXiv 2024

  39. [39]

    Polynomial mixing of the critical ising model on sparse erdos-renyi graphs

    Kyprianos-Iason Prodromidis and Allan Sly. Polynomial mixing of the critical I sing model on sparse E rdos- R enyi graphs. arXiv preprint arXiv:2510.07254 , 2025

    work page arXiv 2025

  40. [40]

    Computational transition at the uniqueness threshold

    Allan Sly. Computational transition at the uniqueness threshold. In FOCS , pages 287--296. IEEE Computer Soc., Los Alamitos, CA, 2010

    work page 2010

  41. [41]

    The computational hardness of counting in two-spin models on d-regular graphs

    Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In FOCS , pages 361--369, 2012

    work page 2012

  42. [42]

    Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

    Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. J. Stat. Phys. , 155(4):666--686, 2014

    work page 2014

  43. [43]

    Swendsen and Jian-Sheng Wang

    Robert H. Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in M onte C arlo simulations. Physical Review Letters , 58(2):86–88, January 1987

    work page 1987

  44. [44]

    Counting independent sets up to the tree threshold

    Dror Weitz. Counting independent sets up to the tree threshold. In STOC , pages 140--149, 2006

    work page 2006