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

← 1 2 →