KAIST Discrete Math Seminar

Approximate random k-colouring of a graph G=(V,E) is a very well
studied problem in computer science, discrete mathematics and
statistical physics. It amounts to constructing a k-colouring of G
which is distributed close to Gibbs distribution in polynomial time.
In this talk, we deal with the problem when the underlying graph is an
instance of Erdos-Renyi random graph G(n,d/n), where d is fixed. In
this paper we propose a novel efficient algorithm for approximate
random k-colouring G(n,d/n). To be more specific, with probability at
least 1-n^-Ω(1) over the input instances G(n,d/n) and for kgeq
(1+ε)d, the algorithm returns a k-colouring which is distributed
within total variation distance n^-Ω(1) from the Gibbs
distribution of the input graph. The algorithm we propose is neither a
MCMC one nor inspired by the message passing algorithms proposed by
statistical physicists. Roughly the idea is as follows: Initially we
remove sufficiently many edges of the input graph. This results in a
graph which can be coloured randomly efficiently. Then we move back
the removed edges one by one. Every time we add an edge we update the
colouring of the graph, with the new edge, so that the colouring
remains (sufficiently) random. The performance depends heavily on
certain spatial correlation decay properties of the Gibbs
distribution.