Premium
Random sampling of 3‐colorings in ℤ 2
Author(s) -
Goldberg Leslie Ann,
Martin Russell,
Paterson Mike
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20002
Subject(s) - glauber , mixing (physics) , markov chain , sampling (signal processing) , mathematics , boundary (topology) , combinatorics , statistical physics , discrete mathematics , physics , statistics , mathematical analysis , quantum mechanics , detector , scattering , optics
We consider the problem of uniformly sampling proper 3‐colorings of an m × n rectangular region of ℤ 2 . We show that the single‐site “Glauber‐dynamics” Markov chain is rapidly mixing. Our result complements an earlier result of Luby, Randall, and Sinclair, which demonstrates rapid mixing when there is a fixed boundary (whose color cannot be changed). © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004