Random sampling of 3‐colorings in ℤ2
Random sampling of 3‐colorings in ℤ2
复制标题
ℤ2 中 3 种颜色的随机采样
DOI：
10.1002/rsa.20002
复制
发表时间：
2004
影响因子：
1
通讯作者：
M. Paterson
中科院分区：
文献类型：
--
作者：
L. A. Goldberg;R. Martin;M. Paterson
本文研究了n × n矩形区域上真3-染色的均匀采样问题。我们证明了单点“Glauber-dynamics”马尔可夫链是快速混合的。我们的结果补充了吕比，兰德尔和辛克莱的早期结果，这表明快速混合时，有一个固定的边界（其颜色不能改变）。© 2004 Wiley Periodicals，Inc.随机结构算法，2004
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