FPTAS conjecture for Potts models on random regular bipartite graphs

Let $G$ be a random $\Delta$ -regular bipartite graph, and let $Z_{G,q}(\beta)$ be the partition function of the anti-ferromagnetic $q$ -state Potts model on $G$ . Random-regular-graph counting conjecture. For $\beta>0$ , with high probability there exists an FPTAS for $Z_{G,q}(\beta)$ . The conjecture concerns efficient approximate counting throughout the stated positive-temperature regime; the paper's methods establish results at low temperature but do not settle the full conjecture.

Sources & referencesView supporting material

Primary source

Zhidan Li, Siyu Liu and Kuan Yang, “Counting and Sampling Anti-ferromagnetic Potts Models on Random Regular Bipartite Graphs in the Non-uniqueness Regime”, arXiv:2606.21250 (2026).

1 week ago

Progress summary

Refreshed 1 week ago

Partially solved

The conjecture remains open, but a recent paper proves efficient approximate counting in a substantial low-temperature range.

The conjecture asserts that, for every positive temperature, the Potts partition function on a random regular bipartite graph can be approximated efficiently with high probability. It is stated as Conjecture 6.4 in the directly relevant paper, which explicitly leaves the full positive-temperature regime unresolved.

2026 low-temperature theorem

The paper proves an FPTAS with high probability over the random graph for sufficiently large $q$ and $]$ under two explicit low-temperature inequalities involving $]$ , $]$ , and $]$ . It also gives an FPAUS in the same regime, despite exponential slow mixing of single-site Glauber dynamics. These results do not imply the conjectured FPTAS for all $]$ and all parameter values.

Current status (as of August 2026): The conjecture is open; efficient approximate counting is established only in the stated low-temperature regime, with no verified full proof or counterexample.

Sources

arxiv.org

No solutions have been posted yet.