Local convergence of random graph colorings

2015/01/26 by Coja-Oghlan, Amin, Efthymiou, Charilaos, Jaafari, Nor · 1 citation
#05C15 #05C80 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1501.06301

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 \em condensation threshold d_c(k), 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 k₀. 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.

Cited by

• Local limit of Prim's algorithm

Related

• Spatial Mixing of Coloring Random Graphs
• A simple algorithm for sampling colourings of G(n,d/n) up to Gibbs Uniqueness Threshold
• The Distant-l Chromatic Number of Random Geometric Graphs
• Linear Programming Bounds for Randomly Sampling Colorings
• Colouring complete bipartite graphs from random lists