pith. sign in

arxiv: 2606.21250 · v1 · pith:XUIH7YFInew · submitted 2026-06-19 · 💻 cs.DS · math.PR

Counting and Sampling Anti-Ferromagnetic Potts Models on Random Regular Bipartite Graphs in the Non-uniqueness Regime

Zhidan Li , Siyu Liu , Kuan Yang This is my paper

Pith reviewed 2026-06-26 12:59 UTC · model grok-4.3

classification 💻 cs.DS math.PR
keywords anti-ferromagnetic Potts modelpartition function approximationpolymer modelsGlauber dynamicsrandom regular bipartite graphsphase transitionnon-uniqueness regime
0
0 comments X

The pith

A deterministic polymer-model algorithm approximates the partition function of the anti-ferromagnetic multi-state Potts model on random regular bipartite graphs at low temperature while Glauber dynamics mixes slowly.

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

The paper establishes that the anti-ferromagnetic multi-state Potts model on random regular bipartite graphs undergoes a phase transition at low temperature, allowing a deterministic approximation algorithm for the partition function via abstract polymer models while single-site Glauber dynamics exhibits exponentially slow mixing. This generalizes earlier results on anti-ferromagnetic Ising models to the multi-state case. A sympathetic reader cares because the result ties the physical phase transition directly to computational tractability of the partition function on expander-like graphs. The approach relies on the graphs being good bipartite expanders with high probability.

Core claim

On random regular bipartite graphs, when temperature is low enough relative to degree that the non-uniqueness regime holds, the abstract polymer model framework yields a deterministic approximation algorithm for the partition function of the anti-ferromagnetic multi-state Potts model; simultaneously, the single-site Glauber dynamics has exponentially slow mixing time.

What carries the argument

The abstract polymer model framework, which reduces the partition function to a sum over weighted clusters whose decay properties enable efficient approximation.

If this is right

  • The partition function admits a deterministic polynomial-time approximation when temperature is low enough for the polymer model to apply.
  • Single-site Glauber dynamics requires exponential time to mix for the anti-ferromagnetic Potts model in this regime.
  • The result extends the slow-mixing and polymer-approximation dichotomy from the Ising case to arbitrary numbers of states.
  • The expansion properties of random regular bipartite graphs are sufficient to guarantee the polymer decay conditions hold.

Where Pith is reading between the lines

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

  • Similar polymer techniques may extend to approximating partition functions on other families of good expanders beyond bipartite regular graphs.
  • The exponential slowdown of Glauber dynamics suggests that other local Markov chains may also fail to mix rapidly in the same temperature range.
  • One could test whether the approximation algorithm remains efficient when the graph is a deterministic expander rather than a random one.

Load-bearing premise

The temperature must be sufficiently low relative to the graph degree so that the non-uniqueness regime holds and the polymer representation applies on the random regular bipartite graphs.

What would settle it

An explicit computation on a large random regular bipartite graph showing that single-site Glauber dynamics reaches equilibrium in polynomial time at the claimed low temperature would falsify the slow-mixing claim.

read the original abstract

The anti-ferromagnetic multi-state Potts model, a generalization of the Ising model, is one of the most fundamental models in statistical physics. It was conjectured by Koteck\'{y} (Phys.~Rev.~B, 1985) that the model undergoes a phase transition from a disordered phase at infinite temperature to an ordered phase at sufficiently low temperature on lattices. Such phase transitions are believed to play an important role in computational complexity theory and remain closely connected to the problem of approximating the partition function of the system. For proper three-coloring models (corresponding to the zero-temperature), torpid mixing of a family of local-update Markov chains on lattices was established by Galvin, Kahn, Randall and Sorkin (SIDMA, 2015), coinciding with the presence of phase coexistence following shown by Feldheim and Spinka (J.~Eur.~Math.~Soc., 2019). In this work, we study approximating the partition function of the anti-ferromagnetic multi-state Potts model at low temperature on random regular bipartite graphs, which are with high probability good bipartite expanders. On the negative side, we generalize the result by Geisler, Kang, Sarantis and Wdowinski (arXiv, 2026) for anti-ferromagnetic Ising models to show that when the temperature is sufficiently low relative to the degree of the underlying graph, the celebrated single-site Glauber dynamics has exponentially slow mixing time. On the positive side, we design a deterministic algorithm that yields an approximation to the partition function of the model via the framework of abstract polymer models as Jenssen, Keevash and Perkins (SICOMP, 2020), Liao, Lin, Lu and Mao (Theor.~Comput.~Sci., 2022), Galanis, Goldberg and Stewart (TOCT, 2021) and Geisler, Kang, Sarantis and Wdowinski (arXiv, 2026).

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

0 major / 3 minor

Summary. The paper claims that for the anti-ferromagnetic multi-state Potts model on random regular bipartite graphs (which are w.h.p. good expanders), when the temperature is low enough to enter the non-uniqueness regime, the single-site Glauber dynamics has exponentially slow mixing time (generalizing the Ising result of Geisler et al.), while a deterministic FPTAS for the partition function exists via the abstract polymer model framework of Jenssen-Keevash-Perkins and subsequent works.

Significance. If the results hold, the work extends the polymer-model FPTAS technique to Potts models on bipartite random regular graphs and pairs it with a matching hardness result for local Markov chains, strengthening the link between phase coexistence and computational intractability for approximation. Credit is due for the explicit generalization of the cluster-expansion convergence arguments from the Ising case to the multi-state Potts setting on the same expander family.

minor comments (3)
  1. [§2.2] §2.2: the precise range of temperatures (or inverse-temperature β) for which the non-uniqueness regime and polymer-model convergence are claimed should be stated explicitly as a function of the degree d and number of states q, rather than left as 'sufficiently low'.
  2. [Theorem 1.2] The statement of Theorem 1.2 (slow mixing) would benefit from a short paragraph comparing the obtained mixing-time lower bound quantitatively with the one in Geisler et al. for the Ising case.
  3. [§3] Notation for the polymer weights and the truncation parameter in the cluster expansion (around Eq. (3.4)) is introduced without an immediate reference back to the general abstract-polymer theorem being invoked; a one-sentence pointer would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external frameworks

full rationale

The paper applies the abstract polymer model framework (cited from Jenssen-Keevash-Perkins SICOMP 2020, Liao et al. TCS 2022, Galanis et al. TOCT 2021, and Geisler et al. arXiv 2026) to approximate the Potts partition function on random regular bipartite graphs in the non-uniqueness regime. The slow-mixing result for Glauber dynamics generalizes the Ising case from Geisler et al. (distinct authors). No load-bearing step reduces by definition, fitted input, or self-citation chain to the paper's own inputs; the adaptation to multi-state Potts and the specific graph class supplies independent content. Expander properties of random regular bipartite graphs are standard external facts. This is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the low-temperature non-uniqueness regime and expander properties of the random graphs; these are domain assumptions drawn from prior statistical physics and graph theory literature rather than new postulates.

axioms (2)
  • domain assumption Random regular bipartite graphs are with high probability good bipartite expanders.
    Invoked in the abstract as the graph class where both the mixing and approximation results hold.
  • domain assumption Temperature is sufficiently low relative to the degree so that the non-uniqueness regime applies.
    Stated as the condition for both the exponential slow mixing and the applicability of the polymer model algorithm.

pith-pipeline@v0.9.1-grok · 5897 in / 1399 out tokens · 31456 ms · 2026-06-26T12:59:07.816490+00:00 · methodology

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

26 extracted references · 15 canonical work pages

  1. [1]

    Uniqueness of the

    Bencs, Ferenc and Boer, David de and Buys, Pjotr and Regts, Guus , date =. Uniqueness of the. Journal of Statistical Physics , number =. 2023 , bdsk-url-1 =. doi:10.1007/s10955-023-03145-z , id =

    work page doi:10.1007/s10955-023-03145-z 2023

  2. [2]

    Deterministic approximate counting of colorings with fewer than

    Ferenc Bencs and Khallil Berrekkal and Guus Regts , url =. Deterministic approximate counting of colorings with fewer than. 2026 , month =. doi:10.46298/theoretics.26.1 , journal =

    work page doi:10.46298/theoretics.26.1 2026

  3. [3]

    Combinatorics, Probability and Computing , author =

    Spectral gap in random bipartite biregular graphs and applications , volume =. Combinatorics, Probability and Computing , author =. 2022 , pages =. doi:10.1017/S0963548321000249 , number =

    work page doi:10.1017/s0963548321000249 2022

  4. [4]

    Sampling in uniqueness from the

    Blanca, Antonio and Galanis, Andreas and Goldberg, Leslie Ann and. Sampling in uniqueness from the. SIAM Journal on Discrete Mathematics , volume =. 2020 , doi =

    2020

  5. [5]

    Random Structures & Algorithms , volume =

    Chen, Zongchen and Galanis, Andreas and Goldberg, Leslie Ann and Perkins, Will and Stewart, James and Vigoda, Eric , title =. Random Structures & Algorithms , volume =. doi:https://doi.org/10.1002/rsa.20968 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20968 , year =

    work page doi:10.1002/rsa.20968

  6. [6]

    and Yinon Spinka , note =

    Feldheim, Ohad N. and Yinon Spinka , note =. Long-range order in the 3 -state antiferromagnetic. Journal of the European Mathematical Society , issn =. 2019 , doi =

    2019

  7. [7]

    , date =

    Greenhill, C. , date =. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs , url =. Computational Complexity , number =. 2000 , bdsk-url-1 =. doi:10.1007/PL00001601 , id =

    work page doi:10.1007/pl00001601 2000

  8. [8]

    2021 , issue_date =

    Galanis, Andreas and Goldberg, Leslie Ann and Stewart, James , title =. 2021 , issue_date =. doi:10.1145/3470865 , journal =

    work page doi:10.1145/3470865 2021

  9. [9]

    2022 , issn =

    Fast mixing via polymers for random graphs with unbounded degree , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.ic.2022.104894 , url =

    work page doi:10.1016/j.ic.2022.104894 2022

  10. [10]

    Electronic Journal of Probability , number =

    Andreas Galanis and Leslie Ann Goldberg and Kuan Yang , title =. Electronic Journal of Probability , number =. 2018 , doi =

    2018

  11. [11]

    Sampling from the antiferromagnetic

    Geisler, Anna and Kang, Mihyun and Sarantis, Michail and Wdowinski, Ronen , year =. Sampling from the antiferromagnetic. arXiv , primaryClass =:2603.02101 , journal =

    arXiv

  12. [12]

    , title =

    Galvin, David and Kahn, Jeff and Randall, Dana and Sorkin, Gregory B. , title =. SIAM Journal on Discrete Mathematics , volume =. 2015 , doi =. https://doi.org/10.1137/12089538X , abstract =

    work page doi:10.1137/12089538x 2015

  13. [13]

    Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region , year =

    Galanis, Andreas and. Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region , year =. doi:10.1145/2785964 , journal =

    work page doi:10.1145/2785964

  14. [14]

    Combinatorics, Probability and Computing , author =

    Inapproximability of the partition function for the antiferromagnetic. Combinatorics, Probability and Computing , author =. 2016 , pages =. doi:10.1017/S0963548315000401 , number =

    work page doi:10.1017/s0963548315000401 2016

  15. [15]

    SIAM Journal on Computing , volume =

    Jenssen, Matthew and Keevash, Peter and Perkins, Will , title =. SIAM Journal on Computing , volume =. 2020 , doi =

    2020

  16. [16]

    Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Li, Liang and Lu, Pinyan and Yin, Yitong , title =. Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611973105.5 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.5 , year =

    work page doi:10.1137/1.9781611973105.5 2013

  17. [17]

    SIAM Journal on Computing , volume =

    Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush , title =. SIAM Journal on Computing , volume =. 2025 , doi =

    2025

  18. [18]

    Long-range order for antiferromagnetic

    Koteck\'. Long-range order for antiferromagnetic. Phys. Rev. B , volume =. 1985 , month =. doi:10.1103/PhysRevB.31.3088 , url =

    work page doi:10.1103/physrevb.31.3088 1985

  19. [19]

    Cluster expansion for abstract polymer models , volume =

    Koteck. Cluster expansion for abstract polymer models , volume =. Communications in Mathematical Physics , number =

  20. [20]

    Liao, Chao and Lin, Jiabao and Lu, Pinyan and Mao, Zhenyu , keywords =. An. Theoretical Computer Science , volume =. 2022 , issn =. doi:https://doi.org/10.1016/j.tcs.2022.07.001 , url =

    work page doi:10.1016/j.tcs.2022.07.001 2022

  21. [21]

    2017 , volume =

    Markov Chains and Mixing Times: Second Edition , author =. 2017 , volume =

    2017

  22. [22]

    Improved

    Lu, Pinyan and Yin, Yitong , editor=. Improved. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , year =

  23. [23]

    SIAM Journal on Computing , volume =

    Patel, Viresh and Regts, Guus , title =. SIAM Journal on Computing , volume =. 2017 , doi =

    2017

  24. [24]

    Mathematical Proceedings of the Cambridge Philosophical Society , author =

    Some generalized order-disorder transformations , volume =. Mathematical Proceedings of the Cambridge Philosophical Society , author =. 1952 , pages =. doi:10.1017/S0305004100027419 , number =

    work page doi:10.1017/s0305004100027419 1952

  25. [25]

    Approximate counting, uniform generation and rapidly mixing Markov chains

    Sinclair, Alistair and Jerrum, Mark , title =. 1989 , issue_date =. doi:10.1016/0890-5401(89)90067-9 , journal =

    work page doi:10.1016/0890-5401(89)90067-9 1989

  26. [26]

    Wormald, N. C. , editor =. Models of Random Regular Graphs , booktitle =. 1999 , pages =

    1999