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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom