Speaker:

Charilaos Efthymiou

Title:

A simple algorithm for random colouring G(n,d/n) using (2+\epsilon)d colours.

Abstract:

Approximate random k-colouring of a graph G=(V,E) is a well-studied problem in computer science and statistical physics. It amounts to constructing a k-colouring of G which is distributed close to Gibbs distribution, i.e. the uniform distribution over all the k-colourings of G.

In this talks we deal with the problem when the underlying graph is an instance of Erdos-Renyi random graph G(n,p), where p=d/n and d is fixed.

I will present a new efficient algorithm for approximate random k-colouring. With probability 1-n^{-\Omega(1)} over the input graph instances G(n,d/n) and for k>(2+\epsilon)d, the algorithm returns a k-colouring distributed within total variation distance 1-n^{-Omega(1)} from the Gibbs distribution.

The algorithm is neither MCMC based nor inspired by the message passing heuristics introduced by statistical physicists. It is a combinatorial one and it is based on the following simple idea. Remove edges of the input graph G(n,d/n) until it becomes so simple that we can take a random colouring efficiently. Random colour this simple subgraph. Then, rebuild the initial graph by adding the deleted edges one by one. Each time we add an edge update the colouring of some vertices so as the colouring of the graph (with the added edge) to be random.