Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-23T15:19:25.872Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2

Published online by Cambridge University Press:  01 February 2010

Leslie Ann Goldberg ,
Markus Jalsenius ,
Russell Martin  and
Mike Paterson
Leslie Ann Goldberg
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, http://www.dcs.warwick.ac.uk/people/academic/Leslie.Goldberg/
Markus Jalsenius
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, http://www.dcs.warwick.ac.uk/~markus
Russell Martin
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, http://www.csc.liv.ac.uk/~martin/
Mike Paterson
Affiliation:
Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom, http://www.dcs.warwick.ac.uk/people/academic/Mike.Paterson/

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The authors of this paper consider the anti-ferromagnetic Potts model on the the integer lattice Z2. The model has two parameters: q, the number of spins, and λ = exp(−β), where β 4 is ‘inverse temperature’. It is known that the model has strong spatial mixing if q > 7, or if q = 7 and λ = 0 or λ > 1/8, or if q = 6 and λ = 0 or λ > 1/4. The λ = 0 case corresponds to the model in which configurations are proper q-colourings of Z2. It is shown that the system has strong spatial mixing for q ≥ 6 and any λ. This implies that Glauber dynamics is rapidly mixing (so there is a fully-polynomial randomised approximation scheme for the partition function), and also that there is a unique infinite-volume Gibbs state. We also show that strong spatial mixing occurs for a larger range of λ than was previously known for q = 3, q = 4 and q = 5.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 9 , 2006 , pp. 1 - 20
Copyright
Copyright © London Mathematical Society 2006

References

1. Achlioptas, D., Molloy, M., Moore, C. and Bussel, F. Van, ‘Sampling grid colorings with fewer colors’, LATIN 2004: Theoretical informatics, Proc. 6th Latin American Symposium, Lecture Notes in Comput. Sci. 2976 (ed. Colton, M. Farach-, Springer, 2004) 80–89.CrossRefGoogle Scholar
2. Bubley, R., Dyer, M., Greenhill, C. and Jerrum, M., ‘On approximately counting colourings of small degree graphs’, SIAM J. Computing 29 (1999) 387–400.CrossRefGoogle Scholar
3. Cesi, F., ‘Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields’, Probab. Theory Related Fields 120 (2001) 569–584.CrossRefGoogle Scholar
4. Dyer, M. and Greenhill, C., ‘Random walks on combinatorial objects’, Surveys in Combinatorics, ed. Lamb, J.D. and Preece, D.A., London Math. Soc. Lecture Note Ser. 267 (Cambridge University Press, 1999) 101–136.Google Scholar
5. Dyer, M., Sinclair, A., Vigoda, E. and Weitz, D., ‘Mixing in time and space for lattice spin systems: a combinatorial view’, Random Structures Algorithms 24 (2004) 461–479.CrossRefGoogle Scholar
6. Goldberg, L.A., Jerrum, M. and Paterson, M., ‘The computational complexity of two-state spin systems’, Random Structures Algorithms 23 (2003) 133–154.CrossRefGoogle Scholar
7. Goldberg, L.A., Martin, R. and Paterson, M., ‘Random sampling of 3-colorings in ℤ2’, Random Structures Algorithms 24 (2004) 279–302.CrossRefGoogle Scholar
8. Goldberg, L.A., Martin, R. and Paterson, M., ‘Strong spatial mixing with fewer colours for lattice graphs’, SIAM J. Comput., to appear.Google Scholar
9. Jaeger, F., Vertigan, D.L. and Welsh, D.J.A., ‘On the computational complexity of the Jones and Tutte polynomials’, Math. Proc. Cambr. Philos. Soc. 108 (1990) 35–53.CrossRefGoogle Scholar
10. Jalsenius, M., PhD thesis, University of Warwick, in preparation.Google Scholar
11. Jerrum, M., ‘A very simple algorithm for estimating the number of k-colourings of a low-degree graph’, Random Structures Algorithms 7 (1995) 157–165.CrossRefGoogle Scholar
12. Jerrum, M. and Sinclair, A., ‘Polynomial-time approximation algorithms for the Ising model’, SIAM J. Comput. 22 (1993) 1087–1116.CrossRefGoogle Scholar
13. Jerrum, M.R., Valiant, L.G. and Vazirani, V.V., ‘Random generation of combinatorial structures from a uniform distribution’, Theoret. Comput. Sci. 43 (1986) 169–188.CrossRefGoogle Scholar
14. Luby, M., Randall, D. and Sinclair, A.J., ‘Markov chain algorithms for planar lattice structures’, SIAM J. Comput. 31 (2001) 167–192.CrossRefGoogle Scholar
15. Martinelli, F., ‘Lectures on Glauber dynamics for discrete spin models’,Lectures on probability theory and statistics (Saint-Flour, 1997), Lecture Notes in Math. 1717 (Springer, Berlin, 1998 93–191.CrossRefGoogle Scholar
16. Martinelli, F. and Olivieri, E., ‘Approach to equilibrium of Glauber dynamics in the one phase region. II: The general case’, Comm. Math. Phys. 161 (1994) 487–514.CrossRefGoogle Scholar
17. Salas, J. and Sokal, A.D., ‘Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem’, J. Statist. Phys. 86 (1997) 551–579.CrossRefGoogle Scholar
18. Stroock, D.W. and Zegarlinski, B., ‘The logarithmic Sobolev inequality for discrete spin systems on a lattice’, Comm. Math. Phys. 149 (1992) 175–194.CrossRefGoogle Scholar
19. Weitz, D., ‘Mixing in time and space for discrete spin systems’, PhD thesis, University of California, Berkeley, 2004.Google Scholar
20. Welsh, D.J.A., Complexity: knots, colourings, and counting, London Math. Soc. Lecture Note Ser. 186 (Cambridge University Press, 1993).CrossRefGoogle Scholar