The Mixing Time of Glauber Dynamics for Colouring Regular Trees
| dc.creator | Goldberg, Leslie Ann | |
| dc.creator | Jerrum, Mark | |
| dc.creator | Karpinski, Marek | |
| dc.date | 2008-06-05 | |
| dc.date.accessioned | 2026-07-07T09:42:49Z | |
| dc.date.available | 2026-07-07T09:42:49Z | |
| dc.description | We consider Metropolis Glauber dynamics for sampling proper $q$-colourings of the $n$-vertex complete $b$-ary tree when $3\leq q\leq b/2\ln(b)$. We give both upper and lower bounds on the mixing time. For fixed $q$ and $b$, our upper bound is $n^{O(b/\log b)}$ and our lower bound is $n^{Ω(b/q \log(b))}$, where the constants implicit in the $O()$ and $Ω()$ notation do not depend upon $n$, $q$ or $b$. | |
| dc.identifier | https://arxiv.org/abs/0806.0921 | |
| dc.identifier | http://arxiv.org/abs/0806.0921 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162327 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.title | The Mixing Time of Glauber Dynamics for Colouring Regular Trees | |
| dc.type | text |