2026-07-24T03:00:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5332 2024-03-06T10:36:20Z ddc:004 open_access

Local Convergence of Random Graph Colorings Coja-Oghlan, Amin Efthymiou, Charilaos Jaafari, Nor Random graph Galton-Watson tree phase transitions graph coloring Gibbs distribution convergence 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 condensation threshold d_c, the colors assigned to far away vertices are asymptotically independent [Krzakala et al: PNAS 2007]. We prove this conjecture for k exceeding a certain constant k_0. More generally, we determine the joint distribution of the k-colorings that Sigma induces locally on the bounded-depth neighborhoods of a fixed number of vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amin Coja-Oghlan and Charilaos Efthymiou and Nor Jaafari 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.726 urn:nbn:de:0030-drops-53321 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.726 eng https://creativecommons.org/licenses/by/3.0/legalcode