{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:27Z","timestamp":1725574107122},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212584"},{"type":"electronic","value":"9783540246985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24698-5_12","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:28:22Z","timestamp":1294439302000},"page":"80-89","source":"Crossref","is-referenced-by-count":26,"title":["Sampling Grid Colorings with Fewer Colors"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Molloy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Van Bussel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Aldous, D.: Random walks on finite groups and rapidly mixing Markov chains. In: Dold, A., Eckmann, B. (eds.) S\u00e9minaire de Probabilit\u00e9s XVII 1981\/82. Springer Lecture Notes in Mathematics, vol.\u00a0986, pp. 243\u2013297 (1986)","DOI":"10.1007\/BFb0068322"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proc. 28th Ann. Symp. on Found. of Comp. Sci., pp. 223\u2013231 (1997)","DOI":"10.1109\/SFCS.1997.646111"},{"key":"12_CR3","unstructured":"Bubley, R., Dyer, M., Greenhill, C.: Beating the 2\u0394 bound for approximately counting colourings: A computer-assisted proof of rapid mixing. In: Proc. 9th Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 355\u2013363 (1998)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/PL00008792","volume":"120","author":"F. Cesi","year":"2001","unstructured":"Cesi, F.: Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probability Theory and Related Fields\u00a0120, 569\u2013584 (2001)","journal-title":"Probability Theory and Related Fields"},{"key":"12_CR5","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1214\/aoap\/1034968224","volume":"6","author":"P. Diaconis","year":"1996","unstructured":"Diaconis, P., Saloff-Coste, L.: Comparison theorems for reversible Markov chains. Annals of Applied Probability\u00a06, 696\u2013730 (1996)","journal-title":"Annals of Applied Probability"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1214\/aoap\/1177005980","volume":"1","author":"P. Diaconis","year":"1991","unstructured":"Diaconis, P., Stroock, D.: Geometric bounds for eigenvalues of Markov chains. Annals of Applied Probability\u00a01, 36\u201361 (1991)","journal-title":"Annals of Applied Probability"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<285::AID-RSA6>3.0.CO;2-R","volume":"13","author":"M. Dyer","year":"1998","unstructured":"Dyer, M., Greenhill, C.: A more rapidly mixing Markov chain for graph colorings. Random Structures and Algorithms\u00a013, 285\u2013317 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"12_CR8","first-page":"101","volume-title":"Surveys in Combinatorics","author":"M. Dyer","year":"1999","unstructured":"Dyer, M., Greenhill, C.: Random walks on combinatorial objects. In: Lamb, J., Preece, D. (eds.) Surveys in Combinatorics, pp. 101\u2013136. Cambridge University Press, Cambridge (1999)"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-45726-7_13","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Dyer","year":"2002","unstructured":"Dyer, M., Sinclair, A., Vigoda, E., Weitz, D.: Mixing in time and space for lattice spin systems: A combinatorial view. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 149\u2013163. Springer, Heidelberg (2002)"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1023\/A:1004599121565","volume":"96","author":"S. Ferreira","year":"1999","unstructured":"Ferreira, S., Sokal, A.: Antiferromagnetic Potts models on the square lattice: a high-precision Monte Carlo study. J. Statistical Physics\u00a096, 461\u2013530 (1999)","journal-title":"J. Statistical Physics"},{"key":"12_CR11","unstructured":"Goldberg, L., Martin, R., Paterson, M.: Random sampling of 3-colourings in \u21242. Random Structures and Algorithms (to appear)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M. Jerrum","year":"1995","unstructured":"Jerrum, M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures and Algorithms\u00a07, 157\u2013165 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S0097539799360355","volume":"31","author":"M. Luby","year":"2001","unstructured":"Luby, M., Randall, D., Sinclair, A.: Markov chain algorithms for planar lattice structures. SIAM Computing\u00a031, 167\u2013192 (2001)","journal-title":"SIAM Computing"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on Probability Theory and Statistics, Saint-Flour 1997. Springer Lecture Notes in Mathematics, vol.\u00a01717, pp. 93\u2013191 (1999)","DOI":"10.1007\/978-3-540-48115-7_2"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1023\/A:1018627008925","volume":"99","author":"C. Moore","year":"2000","unstructured":"Moore, C., Newman, M.: Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet. J. Stat. Phys.\u00a099, 661\u2013690 (2000)","journal-title":"J. Stat. Phys."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"5344","DOI":"10.1103\/PhysRevE.60.5344","volume":"60","author":"C. Moore","year":"1999","unstructured":"Moore, C., Nordahl, M., Minar, N., Shalizi, C.: Vortex dynamics and entropic forces in antiferromagnets and antiferromagnetic Potts models. Physical Review E\u00a060, 5344\u20135351 (1999)","journal-title":"Physical Review E"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"1598","DOI":"10.1063\/1.533199","volume":"41","author":"D. Randall","year":"2000","unstructured":"Randall, D., Tetali, P.: Analyzing Glauber dynamics by comparison of Markov chains. J. Mathematical Physics\u00a041, 1598\u20131615 (2000)","journal-title":"J. Mathematical Physics"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02199113","volume":"86","author":"J. Salas","year":"1997","unstructured":"Salas, J., Sokal, A.: Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Statistical Physics\u00a086, 551\u2013579 (1997)","journal-title":"J. Statistical Physics"},{"key":"12_CR19","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-1-4612-0323-0","volume-title":"Algorithms for random generation and counting: a Markov chain approach","author":"A. Sinclair","year":"1993","unstructured":"Sinclair, A.: Algorithms for random generation and counting: a Markov chain approach, pp. 47\u201348. Birkhauser, Boston (1993)"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A. Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation, and rapidly mixing Markov chains. Information and Computation\u00a082, 93\u2013133 (1989)","journal-title":"Information and Computation"},{"key":"#cr-split#-12_CR21.1","unstructured":"Sokal, A.: A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models. Talk presented at the conference on Inhomogeneous Random Systems, Universit\u00e9 de Cergy-Pontoise (January 2000);"},{"key":"#cr-split#-12_CR21.2","unstructured":"Markov Processes and Related Fields\u00a07, 21\u201338 (2001)"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1063\/1.533196","volume":"41","author":"E. Vigoda","year":"2000","unstructured":"Vigoda, E.: Improved bounds for sampling colorings. J. Mathematical Physics\u00a041, 1555\u20131569 (2000)","journal-title":"J. Mathematical Physics"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1103\/PhysRevLett.63.109","volume":"63","author":"J. Wang","year":"1989","unstructured":"Wang, J., Swendsen, R., Koteck\u00fd, R.: Physical Review Letters\u00a063, 109 (1989)","journal-title":"Physical Review Letters"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"2465","DOI":"10.1103\/PhysRevB.42.2465","volume":"42","author":"J. Wang","year":"1990","unstructured":"Wang, J., Swendsen, R., Koteck\u00fd, R.: Physical Review B\u00a042, 2465 (1990)","journal-title":"Physical Review B"}],"container-title":["Lecture Notes in Computer Science","LATIN 2004: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24698-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T02:56:12Z","timestamp":1637117772000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24698-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212584","9783540246985"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24698-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}