The Glauber Dynamics for Colourings of Bounded Degree Trees

被引:0
作者
Lucier, Brendan [1 ]
Molloy, Michael [1 ]
Peres, Yuval [2 ]
机构
[1] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 1A1, Canada
[2] Microsoft Res, Redmond, WA USA
来源
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES | 2009年 / 5687卷
关键词
SAMPLING COLORINGS; INDEPENDENT SETS; GRAPH;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the Glauber dynamics Markov chain for k-colourings of trees with maximum degree Delta. For k >= 3, we show that the mixing time on every tree is at most n(O(1+Delta/(k log Delta))). This bound is tight up to the constant factor in the exponent, as evidenced by the complete tree. Our proof uses a weighted canonical paths analysis and a variation of the block dynamics that exploits the differing relaxation times of blocks.
引用
收藏
页码:631 / +
页数:3
相关论文
共 20 条
[1]  
[Anonymous], 1869, Journal f ur die reine und angewandte Mathematik, DOI DOI 10.1515/CRLL.1869.70.185
[2]  
[Anonymous], 1991, The annals of applied probability, DOI DOI 10.1214/AOAP/1177005980
[3]   Glauber dynamics on trees and hyperbolic graphs [J].
Berger, N ;
Kenyon, C ;
Mossel, E ;
Peres, Y .
PROBABILITY THEORY AND RELATED FIELDS, 2005, 131 (03) :311-340
[4]  
Brightwell GR, 2002, BOLYAI MATH STUD, V10, P247
[5]  
DIACONIS P., 1993, The Annals of Applied Probability, V3, P696, DOI DOI 10.1214/AOAP/1177005359
[6]   Systematic scan for sampling colorings [J].
Dyer, M ;
Goldberg, LA ;
Jerrum, M .
ANNALS OF APPLIED PROBABILITY, 2006, 16 (01) :185-230
[7]  
GOLDBERG L, 2008, ARXIV08060921V1
[8]  
HAYES T, 2007, P STOC 2007
[9]   A VERY SIMPLE ALGORITHM FOR ESTIMATING THE NUMBER OF K-COLORINGS OF A LOW-DEGREE GRAPH [J].
JERRUM, M .
RANDOM STRUCTURES & ALGORITHMS, 1995, 7 (02) :157-165
[10]   APPROXIMATING THE PERMANENT [J].
JERRUM, M ;
SINCLAIR, A .
SIAM JOURNAL ON COMPUTING, 1989, 18 (06) :1149-1178