Local convergence of random graph colorings

DOI10.1007/S00493-016-3394-XzbMATH Open1399.05200arXiv1501.06301OpenAlexW3008726683MaRDI QIDQ722328FDOQ722328

Authors: Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari 

Publication date: 23 July 2018

Published in: Combinatorica (Search for Journal in Brave)

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 $sigma$ 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_0$. More generally, we investigate the joint distribution of the $k$-colorings that $sigma$ induces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on the reconstruction problem.

Full work available at URL: https://arxiv.org/abs/1501.06301

Recommendations

• Local convergence of random graph colorings
• Planting colourings silently
• On the number of solutions in random graph \(k\)-colouring
• Constraining the clustering transition for colorings of sparse random graphs
• scientific article; zbMATH DE number 5279368

zbMATH Keywords

random graph colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Graph Theory and Probability
• Title not available (Why is that?)
• The two possible values of the chromatic number of a random graph
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Decay of correlations for the hardcore model on the \(d\)-regular random graph
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Expose-and-merge exploration and the chromatic number of a random graph
• Coloring random graphs
• Randomly coloring random graphs
• On colouring random graphs
• The chromatic number of random graphs
• Information, Physics, and Computation
• The condensation phase transition in random graph coloring
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The concentration of the chromatic number of random graphs
• Title not available (Why is that?)
• The freezing threshold for \(k\)-colourings of a random graph
• The chromatic number of random graphs
• The weak limit of Ising models on locally tree-like graphs
• A note on the sharp concentration of the chromatic number of random graphs
• The cavity method at zero temperature
• Reconstruction for Colorings on Trees
• Reconstruction and clustering in random constraint satisfaction problems
• Quiet planting in the locked constraint satisfaction problems
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Reconstruction of random colourings
• Switching colouring of \(G(n,d/n)\) for sampling up to Gibbs uniqueness threshold
• Equivalence of ferromagnetic spin models on trees and random graphs
• Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
• On the method of typical bounded differences
• Large deviations of empirical neighborhood distribution in sparse random graphs

Cited In (9)

• Local convergence of random graph colorings
• Deterministic counting of graph colourings using sequences of subgraphs
• Localisation-resistant random words with small alphabets
• The freezing threshold for \(k\)-colourings of a random graph
• Title not available (Why is that?)
• Planting colourings silently
• Constraining the clustering transition for colorings of sparse random graphs
• On the number of solutions in random graph \(k\)-colouring
• Title not available (Why is that?)

This page was built for publication: Local convergence of random graph colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722328)