The ACO Seminar (2015–2016)

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₀, which depends on the expected degree d, such that the following is true: When the number of colours k is greater than k₀ there is non-reconstruction while when k<k₀ there is reconstruction.

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₀, 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.