Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-23T12:23:38.024Z Has data issue: false hasContentIssue false
  • English
  • Français

Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice

Published online by Cambridge University Press:  01 February 2010

Markus Jalsenius
Markus Jalsenius
Affiliation:
Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, United Kingdom, www.cs.bris.ac.uk/home/markus/

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.

We consider proper 5-colourings of the kagome lattice. Proper q-colourings correspond to configurations in the zero-temperature q-state anti-ferromagnetic Potts model. Salas and Sokal have given a computer assisted proof of strong spatial mixing on the kagome lattice for q ≥ 6 under any temperature, including zero temperature. It is believed that there is strong spatial mixing for q ≥ 4. Here we give a computer assisted proof of strong spatial mixing for q = 5 and zero temperature. It is commonly known that strong spatial mixing implies that there is a unique infinite-volume Gibbs measure and that the Glauber dynamics is rapidly mixing. We give a proof of rapid mixing of the Glauber dynamics on any finite subset of the vertices of the kagome lattice, provided that the boundary is free (not coloured). The Glauber dynamics is not necessarily irreducible if the boundary is chosen arbitrarily for q = 5 colours. The Glauber dynamics can be used to uniformly sample proper 5-colourings. Thus, a consequence of rapidly mixing Glauber dynamics is that there is fully polynomial randomised approximation scheme for counting the number of proper 5-colourings.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 12 , 2009 , pp. 195 - 227
Copyright
Copyright © London Mathematical Society 2009

References

1.Achlioptas, D., Molloy, M., Moore, C. and Van Bussel, F., ‘Sampling grid colorings with fewer colours.’ ‘LATIN 2004: Theoretical Informatics,’ (Springer, 2004), vol. 2976 of Lecture Notes in Computer Science pp. 80–89.Google Scholar
2.Aldous, D., ‘Random walks on finite groups and rapidly mixing Markov chains.’ ‘Seminar on Probability, XVII,’ (Springer, 1983), vol. 986 of Lecture Notes in Mathematics pp. 243–297.Google Scholar
3.Bubley, R. and Dyer, M., ‘Path coupling: a technique for proving rapid mixing in Markov chains.’ ‘FOCS ';97: Proceedings of the 38th Symposium on Foundations of Computer Science,’ (IEEE Computer Society Press, 1997) pp. 223–231.Google Scholar
4.Diaconis, P. and Saloff-Coste, L., ‘Comparison theorems for reversible Markov chains.’ Annals of Applied Probability 3 (1993) 696–730.CrossRefGoogle Scholar
5.Diaconis, P. and Stroock, D., ‘Geometric bounds for eigenvalues of Markov chains.’ Annals of Applied Probability 1 (1991) 36–61.Google Scholar
6.Dyer, M., Goldberg, L. A., Jerrum, M. and Martin, R., ‘Markov chain comparison.’ Probability Surveys 3 (2006) 89–111.CrossRefGoogle Scholar
7.Dyer, M. and Greenhill, C., ‘Random walks on combinatorial objects.’ ‘Surveys in Combinatorics,’ (Cambridge University Press, 1999), vol. 267 of London Mathematical Society Lecture Note Series pp. 101–136.Google Scholar
8.Dyer, M., Sinclair, A., Vigoda, E. and Weitz, D., ‘Mixing in time and space for lattice spin systems: a combinatorial view.’ Random Structures and Algorithms 24 (2004) 461–479.CrossRefGoogle Scholar
9.Georgii, H.-O., Gibbs measures and phase transitions. de Gruyter Studies in Mathematics 9 (Walter de Gruyter & Co., Berlin, Germany, 1988).CrossRefGoogle Scholar
10.Georgii, H.-O., Häggström, O. and Maes, C., ‘The random geometry of equilibrium phases.’ Phase Transitions and Critical Phenomena 18 (2001) 1–142.Google Scholar
11.Goldberg, L. A., Jalsenius, M., Martin, R. and Paterson, M., ‘Improved mixing bounds for the anti-ferromagnetic potts model on ℤ2.’ LMS Journal of Computation and Mathematics 9 (2006) 1–20.CrossRefGoogle Scholar
12.Goldberg, L. A., Martin, R. and Paterson, M., ‘Strong spatial mixing with fewer colours for lattice graphs.’ SIAM Journal on Computing 35 (2005) 486–517.CrossRefGoogle Scholar
13.Jalsenius, M., ‘Strong spatial mixing and rapid mixing with 9 colours for the triangular lattice.’ arXiv:0706.0489v1 [math-ph], (2007).Google Scholar
14.Jerrum, M., ‘A very simple algorithm for estimating the number of k-colorings of a low-degree graph.’ Random Structures and Algorithms 7 (1995) 157–165.Google Scholar
15.Jerrum, M., Counting, Sampling and Integrating: Algorithms and Complexity (Birkhäuser, Basel, Switzerland, 2003).CrossRefGoogle Scholar
16.Jerrum, M., Valiant, L. and Vazirani, V., ‘Random generation of combinatorial structures from a uniform distribution.’ Theoretical Computer Science 43 (1986) 169–188.Google Scholar
17.Martinelli, F., ‘Lectures on Glauber dynamics for discrete spin models.’ ‘Lectures on Probability Theory and Statistics (Saint-Flour, 1997),’ (Springer, 1999), vol. 1717 of Lecture Notes in Mathematics pp. 93–191.Google Scholar
18.Molloy, M., ‘Very rapidly mixing Markov chains for 2Δ-colourings and for independent sets in a 4-regular graph.’ Random Structures and Algorithms 18 (2001) 101–115.3.0.CO;2-D>CrossRefGoogle Scholar
19.Randall, D. and Tetali, P., ‘Analyzing Glauber dynamics by comparison of Markov chains.’ Journal of Mathematical Physics 41 (2000) 1598–1615.Google Scholar
20.Salas, J. and Sokal, A. D., ‘Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem.’ Journal of Statistical Physics 86 (1997) 551.CrossRefGoogle Scholar
21.Sinclair, A., ‘Improved bounds for mixing rates of Markov chains and multicommodity flow.’ Combinatorics, Probability and Computing 1 (1992) 351–370.CrossRefGoogle Scholar
22.Vigoda, E., ‘Improved bounds for sampling colourings.’ Journal of Mathematical Physics 41 (2000) 1555–1569.CrossRefGoogle Scholar
23.Weitz, D., ‘Mixing in time and space for discrete spin systems.’ Ph.D. thesis, University of California, Berkley, (2004).Google Scholar
24.Weitz, D., ‘Combinatorial criteria for uniqueness of Gibbs measures.’ Random Structures and Algorithms 27 (2005) 445–475.CrossRefGoogle Scholar
25.Weitz, D., ‘Counting independent sets up to the tree threshold.’ ‘STOC ’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing,’ (ACM Press, 2006) pp. 140–149.Google Scholar