Probability Seminar: Nayantara Bhatnagar

  • Date: 02/01/2012
  • Time: 15:00
Lecturer(s):
Nayantara Bhatnagar
Location: 

University of British Columbia

Topic: 

Reconstruction for Colorings on Trees

Description: 

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)

Other Information: 

Location: Math 126

 

For more information please visit UBC Math Department

Sponsor: