THE GLAUBER DYNAMICS OF COLORINGS ON TREES IS RAPIDLY MIXING THROUGHOUT THE NONRECONSTRUCTION REGIME

• 成果类型: Article
• 署名作者: Sly, Allan; Zhang, Yumeng
• 署名单位: Australian National University; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1253
• 发表日期: 2017
• 页码: 2646-2674
• 关键词: regular trees; reconstruction; time

摘要

The mixing time of the Glauber dynamics for spin systems on trees is closely related to the reconstruction problem. Martinelli, Sinclair and Weitz established this correspondence for a class of spin systems with soft constraints bounding the log-Sobolev constant by a comparison with the block dynamics [ Comm. Math. Phys. 250 (2004) 301-334; Random Structures Algorithms 31 (2007) 134-172]. However, when there are hard constraints, the dynamics inside blocks may be reducible. We introduce a variant of the block dynamics extending these results to a wide class of spin systems with hard constraints. This applies to essentially any spin system that has nonreconstruction provided that on average the root is not locally frozen in a large neighborhood. In particular, we prove that the mixing time of the Glauber dynamics for colorings on the regular tree is O(nlog n) in the entire nonreconstruction regime.