Probability Seminar: Nayantara Bhatnagar
- Date: 02/01/2012
- Time: 15:00
University of British Columbia
Reconstruction for Colorings on Trees
Abstract:
For spin systems on a tree, roughly, the reconstruction problem is to
determine whether correlations persist between vertices deep inside the
tree and the root. Reconstruction on trees plays an important role in
explaining threshold phenomena in random constraint satisfaction
problems on sparse random graphs as well as the efficiency of finding
and sampling solutions for these problems.
In this talk, I will speak about the following results:
(1) Bounds on the reconstruction threshold for colorings and rapid
mixing of the block dynamics for sampling colorings. (with Vera, Vigoda,
and Weitz '11)
(2) An algorithm to compute the reconstruction threshold, with an
application showing bounds on the threshold for the Potts model on
small-degree trees. (with Maneva '11)