SCIENCE@home

Local Convergence of Random Graph Colorings

A. Coja-Oghlan,Charilaos Efthymiou,Nor Jaafari

Published 2015 in Combinatorica

ABSTRACT

Let G = G(n, m) be a random graph whose average degree d = 2m/n is below the k-colorability threshold. If we sample a k-coloring σ of G uniformly at random, what can we say about the correlations between the colors assigned to vertices that are far apart? According to a prediction from statistical physics, for average degrees below the so-called condensation threshold dk,cond, the colors assigned to far away vertices are asymptotically independent [Krzakala et al.: Proc. National Academy of Sciences 2007]. We prove this conjecture for k exceeding a certain constant k0. More generally, we investigate the joint distribution of the k-colorings that σ induces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on the reconstruction problem.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-58 of 58 references · Page 1 of 1

CITED BY

Showing 1-12 of 12 citing papers · Page 1 of 1