*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Note: Talk will be held in Marcus 1117-1118.
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Reconstruction thresholds for the random colourings of G(n,m)
Abstract:
In this talk we consider the reconstruction problem for the random colourings of a random graph G(n,m) of degree d.
For some k-colourable graph G, the reconstruction problem studies the correlation between the assignment of a single vertex in G and that of its neighbours at distance r, under the uniform measure over the k-colourings of G. This is point to set correlation.
When the correlation persists as r grows, then we have reconstruction, otherwise we have non-reconstruction.
It has been conjecture from statistical physics that for typical instances of G(n,m) the transition from non-reconstruction to reconstruction exhibits a threshold behavior. That is, there is a critical value k_0, which depends on the expected degree d, such that the following is true: When k>k_0 there is non-reconstruction while when k<k_0 there is reconstruction.
The aforementioned phase transition has been related to the performance of local search algorithms as well as the shattering phenomenon in the solution space of the k-colourings.
In this talk I discuss our recent results which show that the phase transition from statistical physics is indeed correct. Moreover, the point where this phase transition occurs, up to smaller order terms, is exactly at the point where it has been conjectured to be.
The first step in our approach is to show that the Gibbs distribution over the k-colouring of G(n,m) converges locally to the Gibbs distribution over the k-colourings of a Poisson(d) Galton-Watson tree T(d), for a wide range of k. This allows to reduce our initial problem to studying the reconstruction on T(d). The second step is to establish the reconstruction threshold for the colourings of T(d).
This talk is based on 2 recent works of mine. One of them is a joint work with Amin Coja-Oghlan and Nor Jaafari.
