Local convergence of random graph colorings

DOI10.1007/S00493-016-3394-XMaRDI QIDQ722328zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari

Publication date 23 July 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.06301, https://drops.dagstuhl.de/opus/volltexte/2015/5332/

zbMATH Keywords

random graph colorings

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)