Feb. 4, 3:30pm, Wean 8220

Charilaos Efthymiou, Georgia Tech

Reconstruction thresholds for the random colourings of*G*(*n*,*m*)

Charilaos Efthymiou, Georgia Tech

Reconstruction thresholds for the random colourings of

Abstract:

In this talk we consider the reconstruction problem for the random colourings of a random graph *G*(*n*,*m*) with expected degree *d*.

For some *k*-colourable graph *G*, consider the uniform measure over its
*k*-colourings. The reconstruction problem studies the correlation between the colour assignment of a single vertex in *G* and that of its neighbours at distance *r*, under the uniform measure. This is a point to set correlation.

When the correlation persists as *r* grows, then we have reconstruction, otherwise we have non-reconstruction.

It has been conjecture in 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

The aforementioned phase transition has been related to the performance of local search algorithms for colouring G(n,m) as well as the geometry of the space of colourings (shattering phenomenon).

In this talk we give a high-level description of the reconstruction problem and its consequences. We discuss our recent results which show that the conjectured phase transition from
statistical physics is indeed correct. Moreover, we compute the critical value *k _{0}*, up to smaller order terms.

This talk is based on 2 recent works of mine. One of them is a joint work with Amin Coja-Oghlan and Nor Jaafari.