Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 12 avril 2011 à 14h00 en B311, Juan Vera Lizcano nous parlera de : Phase transition for the mixing time of Glauber dynamics on regular trees at reconstruction: colorings and independent sets

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.

 [Slides.pdf]


Dernière modification : Monday 18 March 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr