Planting colourings silently

DOI10.1017/S0963548316000390zbMATH Open1371.05068arXiv1411.0610MaRDI QIDQ5366948FDOQ5366948

Authors: Victor Bapst, Amin Coja-Oghlan, Charilaos Efthymiou 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Let $kgeq3$ be a fixed integer and let $Z_k(G)$ be the number of $k$-colourings of the graph $G$. For certain values of the average degree, the random variable $Z_k(G(n,m))$ is known to be concentrated in the sense that $frac1n(ln{Z}_k(G(n,m))-lnE[Z_k(G(n,m))])$ converges to $0$ in probability [Achlioptas and Coja-Oghlan: FOCS 2008]. In the present paper we prove a significantly stronger concentration result. Namely, we show that for a wide range of average degrees, $frac1omega(ln{Z}_k(G(n,m))-lnE[Z_k(G(n,m))])$ converges to $0$ in probability for any diverging function $omega=omega(n)oinfty$. For $k$ exceeding a certain constant $k_0$ this result covers all average degrees up to the so-called condensation phase transition, and this is best possible. As an application, we show that the experiment of choosing a $k$-colouring of the random graph $G(n,m)$ uniformly at random is contiguous with respect to the so-called "planted model".

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

Recommendations

• On the number of solutions in random graph \(k\)-colouring
• Local convergence of random graph colorings
• scientific article; zbMATH DE number 1380613
• Why almost all \(k\)-colorable graphs are easy to color
• Random regular graphs of non-constant degree: concentration of the chromatic number

zbMATH Keywords

planted modelcondensation phase transition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths in graphs
• The two possible values of the chromatic number of a random graph
• Title not available (Why is that?)
• 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
• 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?)
• Almost all regular graphs are hamiltonian
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The freezing threshold for \(k\)-colourings of a random graph
• The chromatic number of random graphs
• A note on the sharp concentration of the chromatic number of random graphs
• Upper-bounding the \(k\)-colorability threshold by counting covers
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Reconstruction and clustering in random constraint satisfaction problems
• Quiet planting in the locked constraint satisfaction problems
• Switching colouring of \(G(n,d/n)\) for sampling up to Gibbs uniqueness threshold
• On the chromatic number of random \(d\)-regular graphs
• Going after the \(k\)-SAT threshold
• On the chromatic number of random regular graphs
• Frozen variables in random Boolean constraint satisfaction problems
• The decimation process in random \(k\)-SAT

Cited In (12)

• Deterministic counting of graph colourings using sequences of subgraphs
• Rigid colorings of hypergraphs and contiguity
• Phase transitions in discrete structures
• Charting the replica symmetric phase
• Constraining the clustering transition for colorings of sparse random graphs
• Local convergence of random graph colorings
• The replica symmetric phase of random constraint satisfaction problems
• On the number of solutions in random hypergraph 2-colouring
• Satisfiability thresholds for regular occupation problems
• On the connectivity of proper colorings of random graphs and hypergraphs
• On the number of solutions in random graph \(k\)-colouring
• Frozen 1-RSB structure of the symmetric Ising perceptron

This page was built for publication: Planting colourings silently

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