text: Let @math be a fixed integer and let @math be the number of @math -colourings of the graph @math . For certain values of the average degree, the random variable @math is known to be concentrated in the sense that @math converges to @math 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, @math converges to @math in probability for any diverging function @math . For @math exceeding a certain constant @math 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 @math -colouring of the random graph @math uniformly at random is contiguous with respect to the so-called "planted model".
  @cite_19: Random instances of constraint satisfaction problems (CSPs) appear to be hard for all known algorithms when the number of constraints per variable lies in a certain interval. Contributing to the general understanding of the structure of the solution space of a CSP in the satisfiable regime, we formulate a set of technical conditions on a large family of random CSPs and prove bounds on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and the threshold for an appropriate reconstruction problem on the CSPs. The bounds become asymptoticlally tight as the number of degrees of freedom in each clause diverges. The families are general enough to include commonly studied problems such as random instances of Not-All-Equal SAT, k-XOR formulae, hypergraph 2-coloring, and graph k-coloring. An important new ingredient is a condition involving the Fourier expansion of clauses, which characterizes the class of ...
summary: We expect that the present approach of combining the second moment method with small subgraph conditioning can be applied successfully to a variety of other random constraint problems. Immediate examples that spring to mind include random @math -NAESAT or random @math -XORSAT, random hypergraph @math -colourability or, more generally, the family of problems studied in @cite_19 . (On the other hand, we expect that in problems such as random @math -SAT the logarithm of the number of satisfying assignments exhibits stronger fluctuations, due to a lack of symmetry.)