You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree ($\Delta$) of the underlying graph and the number of colours or spins ($q$) in determining whether the dynamics mixes rapidly or not. We find a lower bound $L$ on the number of colours such that Glauber dynamics is rapidly mixing if at least $L$ colours are used. We give a closely-matching upper bound $U$ on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random $\Delta$-regular graphs when at most $U$ colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree $\Delta$, e.g. toroidal grids for $\Delta = 4$.
[1] N. Alon, A. Frieze, and D. J. A. Welsh, Polynomial time randomised approximation schemes for Tutte-Grothendieck invariants: the dense case, Random Structures and Algorithms 6 (1995), 459-478.
[2] B. Bollob´as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics 1 (1980), 311-316.
[3] C. Borgs, J. T. Chayes, J. H. Kim, A. Frieze, P. Tetali, E. Vigoda and V. H. Vu, Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics, In 40th Annual Symposium on Foundations of Computer Science, IEEE, New York, 1999, pp. 218-229.
[4] R. Bubley and M. Dyer, Path coupling: a technique for proving rapid mixing in Markov chains. In 38th Annual Symposium on Foundations of Computer Science, IEEE, Los Alimitos, 1997, pp. 223-231.
[5] C. Choua, and S. Lib, Spin systems and Political Districting Problem, Journal of Magnetism and Magnetic Materials 310:2-3 (2007), 2889-2891.
[6] M. Dyer, L. Goldberg, C. Greenhill, and M. Jerrum, On the relative complexity of approximate counting problems, Algorithmica 38:3 (2003), 471-500.
[15] T. Hayes, A simple condition implying rapid mixing of single-site dynamics on spin systems, In 47th Annual Symposium on Foundations of Computer Science, IEEE, Berkeley, California, 2006, pp.39-46.
[16] F. Jaeger, D. Vertigan and D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc. 108 (1990), 35-53.
[17] M. R. Jerrum, A very simple algorithm for estimating the number of k-colourings of a low-degree graph, Random Structures and Algorithms 7:2 (1995), 157-165.
[18] M. Jerrum and A. Sinclair, Approximating the permanent, SIAM Journal on Computing 18 (1989), 1149-1178.
[19] M. R. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM Journal of Computing 22 (1993), 1087-1116.
[20] M. Jerrum and A. Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.), PWS, 1996.
[21] D. Karger, A randomised fully polynomial time approximation scheme for the all terminal network reliability problem, SIAM Journal of Computing 29:2 (1999), 492- 514.
[22] F. Martinelli, Lectures on Glauber dynamics for discrete spin models, Lectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Math. 1717, 93-191, Springer, Berlin, 1999.
[23] R. B. Potts, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. 48 (1952), 106-109.
[24] J. Salas and A. Sokal, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, Journal of Statistical Physics 86:3-4 (1997), 551-579.