The random-cluster model is a mathematical framework for studying how connections form in networks, capturing phenomena like magnetism and phase transitions. It has two parameters: one controlling how likely edges are to appear, and one controlling how strongly clusters are rewarded. Special cases include simple random networks and the famous Ising model of magnetism. A central question is how quickly a computer algorithm called Glauber dynamics, which updates the network one edge at a time, can generate a typical sample from this model. This is important because efficient sampling underlies many statistical and computational applications.
The paper focuses on random regular graphs, where every node has exactly the same number of neighbors. For these graphs, physicists and mathematicians have long predicted that sampling should be efficient in two parameter regimes: when the edge probability is low enough, or when it is high enough (above a threshold called the second uniqueness transition). Previous mathematical results confirming the high-probability regime required the clustering parameter to be at least roughly as large as the logarithm of the degree, leaving most cases open. The authors prove that Glauber dynamics mixes in nearly linear time for all clustering weights greater than 2 in the high-probability regime, essentially settling the prediction for random regular graphs.
The technical obstacle is that standard tools, which track how local messages propagate on trees, are not strong enough to cover the full range of parameters. To get around this, the authors develop a bootstrap argument that carefully tracks how disagreements between two coupled copies of the dynamics shrink over time, building on ideas from recent related work. Notably, the paper discloses that the core ideas of the proof were generated by an AI system called GPT-6 combined with a system called Pharos, with the human author then refining and simplifying the resulting proof, making this a striking example of AI-assisted mathematical research.