A Simple Algorithm for Sampling Colourings of G(n, d/n) Up to Gibbs

Uniqueness Threshold

Uniqueness Threshold

Charilaos Efthymiou

Georgia Institute of Technology, Atlanta, GA, USA

Georgia Institute of Technology, Atlanta, GA, USA

2015/6/

**10 Wed**4PM-5PMApproximate 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+ε)d, the algorithm returns a k-colouring which is distributed

within total variation distance n

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.

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 Gibbsdistribution 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.

Tags: CharilaosEfthymiou