Local convergence of random graph colorings (Q722328)

Consider the random graph on \(n\) labelled vertices with \(m\) edges \(G(n,m)\). It is known that, for each fixed \(k\), there is a number \(d_{k\mathrm{-col}}\) (called the condensation threshold) such that provided the average degree \(2m/n<d_{k\mathrm{-col}}-\varepsilon\) \(G(n,m)\) is with high probability properly \(k\)-colourable (i.e. is properly \(k\)-colourable with probability tending to 1 as \(n\rightarrow\infty\)). The paper under review studies, in the regime where the average degree is below the condensation threshold, a proper \(k\)-colouring of \(G\) sampled uniformly at random, and in particular the correlations between the colours of vertices which are far apart. Statistical physics predicts that the colours of vertices which are far enough apart should be asymptotically independent. The main result of this paper is as follows. For any graph \(H\) and vertex \(v_{0}\in V(H)\) and for \(w\in \mathbb N\), let \(\partial^w (H,v_{0})\) be the ball of radius \(w\) about \(v_{0}\) in \(H\). Also let \(Z_{k}(H)\) denote the number of proper \(k\)-colourings of a graph \(H\). Then the result is that, provided \(k\) is large enough, for every vertex \(v_{0}\in V(G)\), w.h.p. every proper \(k\)-colouring of \(\partial^{w}(G,v_{0})\) extends to \((1+o(1))Z_{k}(G)/Z_{k}(\partial^{w}(G,v_{0}))\) proper \(k\)-colourings of \(G\). A second main result is that, again for \(k\) large enough, if we pick a further vertex \(v_{1}\) at random and fix a proper \(k\)-colouring of \(\partial^{w}(G,v_{1})\) then the number of joint extensions of these two local colourings is \((1+o(1))Z_{k}(G)/\left(Z_{k}(\partial^{w}(G,v_{0})) Z_{k}(\partial^{w}(G,v_{0}))\right)\). Indeed a generalisation of this latter result to any fixed number of vertices is also proven. Some links with the reconstruction problem are also indicated. The formal statements involve local weak convergence arguments.