Planting colourings silently

Abstract

Let $k\ge 3$ 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 $\frac{1}{n}(\ln Z_k(G(n,m))-\ln E[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, $\frac{1}{\omega }(\ln Z_k(G(n,m))-\ln E[Z_k(G(n,m))])$ converges to $0$ in probability for any diverging function $\omega =\omega (n)\to \infty$. 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".

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• The condensation phase transition in random graph coloring

Cited by in corpus (4)

• Information-theoretic thresholds from the cavity method
• Charting the replica symmetric phase
• The replica symmetric phase of random constraint satisfaction problems
• Satisfiability Thresholds for Regular Occupation Problems