Résumé : Glauber dynamics is a simple Markov chain used to sample (complex) spin distributions, such as colorings and independent sets, on graphs. We show that the mixing time of the Glauber dynamics for random k-colorings (and for the hard core model with boundary conditions) of the complete tree undergoes a phase transition around the reconstruction threshold. The central element of our result is a general technique that transforms a reconstruction algorithm into a set with poor conductance.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |