{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T03:59:22Z","timestamp":1789876762199,"version":"4.0.1"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We show that for all sufficiently large $d$, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on ${\\mathbb Z}^d$ admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in ${\\mathbb Z}^d$, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex $v$ in the box, then the probability that $v$ gets color 0 is exponentially small in $d$. The proof proceeds through an analysis of a certain type of cutset separating $v$ from the boundary of the box and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on ${\\mathbb Z}^d$. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus ${\\mathbb Z}^d_n$. We show that there is a constant $\\rho \\approx 0.22$ such that for all even $n \\geq 4$ and $d$ sufficiently large, if ${\\mathcal M}$ is a Markov chain on the set of proper 3-colorings of ${\\mathbb Z}^d_n$ that updates the color of at most $\\rho n^d$ vertices at each step and whose stationary distribution is uniform, then the mixing time of ${\\mathcal M}$ (the time taken for ${\\mathcal M}$ to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in $n^{d-1}$.<\/jats:p>","DOI":"10.1137\/12089538x","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T14:49:11Z","timestamp":1438267751000},"page":"1223-1244","source":"Crossref","is-referenced-by-count":12,"title":["Phase coexistence and torpid mixing in the 3-coloring model on ${\\mathbb Z}^d$"],"prefix":"10.1137","volume":"29","author":[{"given":"David","family":"Galvin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeff","family":"Kahn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Randall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, M. Molloy, C. Moore, and F. Van Bussel,\n                      Sampling grid colourings with fewer colours\n                      , in Proceedings of LATIN'04, 2004, pp. 80-89.","DOI":"10.1007\/978-3-540-24698-5_12"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01007649"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275667"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"C. Borgs, J. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, and V. Vu,\n                      Torpid Mixing of some Monte Carlo Markov Chain algorithms in Statistical Physics\n                      , in Proceedings of IEEE FOCS'99, 1999, pp. 218-229.","DOI":"10.1109\/SFFCS.1999.814594"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1899"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1935"},{"key":"atypb7","unstructured":"R. Bubley, M. Dyer, and C. Greenhill,\n                      Beating the $2\\Delta$ bound for approximately counting colourings: A computer-assisted proof of rapid mixing\n                      , in Proceedings of ACM-SIAM SODA'98, 1998, pp. 355-363."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385700007859"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01075682"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1113026"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.05.003"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Frieze and E. Vigoda,\n                      A Survey on the Use of Markov Chains to Randomly Sample Colourings\n                      , in Combinatorics, Complexity and Chance, Oxford University Press, New York, 2007.","DOI":"10.1093\/acprof:oso\/9780198571278.003.0004"},{"key":"atypb14","first-page":"481","volume":"12","author":"Galvin D.","year":"2007","journal-title":"Sampling 3-colourings of regular bipartite graphs, Electron. J. Probab."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20223"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303006035"},{"key":"atypb17","first-page":"376","author":"Galvin D.","year":"2007","journal-title":"Proceedings of ACM-SIAM SODA"},{"key":"atypb18","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"H.O. Georgii,\n                      Gibbs Measures and Phase Transitions\n                      , de Gruyter, Berlin, 1988.","DOI":"10.1515\/9783110850147"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20002"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.136.A437"},{"key":"atypb22","unstructured":"T. Hayes and E. Vigoda,\n                      Coupling with the stationary distribution and improved sampling for colorings and independent sets\n                      , in Proceedings of ACM-SIAM SODA'05, 2005, pp. 971-979."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"atypb24","unstructured":"M. Jerrum and A. Sinclair,\n                      The Monte Carlo Markov chain method: An approach to approximate counting and integration\n                      , in Approximation Alorithms for NP-Hard Problems, PWS, Boston, 1996."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.31.3088"},{"key":"atypb26","unstructured":"R. Kotecky\u0301,\n                      private communication\n                      , 1998."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-014-2005-1"},{"key":"atypb28","first-page":"557","volume":"309","author":"Lawler G. F.","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360355"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100019174"},{"key":"atypb31","unstructured":"R. Peled,\n                      High-Dimensional Lipschitz Functions are Typically Flat\n                      , arXiv:1005.4636, 2010."},{"key":"atypb32","unstructured":"R. Peled,\n                      private communication\n                      , 2010."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100027419"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1063\/1.533199"},{"key":"atypb35","first-page":"42","volume":"45","author":"Sapozhenko A. A.","year":"1987","journal-title":"Metody Diskret. Analiz."},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"A. J. Sinclair,\n                      Algorithms for Random Generation & Counting: A Markov Chain Approach,\n                      Birkha\u0308user, Boston, 1993.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02124328"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.63.109"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.42.2465"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/12089538X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:36Z","timestamp":1787318256000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/12089538X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/12089538X"],"URL":"https:\/\/doi.org\/10.1137\/12089538x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}