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_26: Given d ?? (0,??) let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d n) is either kd or kd + 1 almost surely.
  @cite_21: In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r‐regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1‐factors in random regular graphs. Moreover, almost all such graphs are r‐edge‐colorable if they have an even number of vertices. Similarly, almost all r‐regular bipartite graphs are hamiltonian and r‐edge‐colorable for fixed r ⩾ 3. © 1994 John Wiley & Sons, Inc.g1
  @cite_6: The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Levy measure. Similar results are found for some related problems. These limit results imply that some different models of random regular graphs are contiguous, which means that they are qualitatively asymptotically equivalent. For example, if r > 3, then the usual (uniformly distributed) random r -regular graph is contiguous to the one constructed by taking the union of r perfect matchings on the same vertex set (assumed to be of even cardinality), conditioned on there being no multiple edges. Some consequences of contiguity for asymptotic distributions are discussed.
  @cite_2: Over the past decade, physicists have developed deep but non-rigorous techniques for studying phase transitions in discrete structures. Recently, their ideas have been harnessed to obtain improved rigorous results on the phase transitions in binary problems such as random @math -SAT or @math -NAESAT (e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous arguments, typically centered around the second moment method, do not extend easily to problems where there are more than two possible values per variable. The single most intensely studied example of such a problem is random graph @math -coloring. Here we develop a novel approach to the second moment method in this problem. This new method, inspired by physics conjectures on the geometry of the set of @math -colorings, allows us to establish a substantially improved lower bound on the @math -colorability threshold. The new lower bound is within an additive @math of a simple first-moment upper bound and within @math of the physics conjecture. By comparison, the best previous lower bound left a gap of about @math , unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004].
  @cite_15: Based on a non-rigorous formalism called the “cavity method”, physicists have put forward intriguing predictions on phase transitions in diluted mean-field models, in which the geometry of interactions is induced by a sparse random graph or hypergraph. One example of such a model is the graph coloring problem on the Erdős–Renyi random graph G(n, d n), which can be viewed as the zero temperature case of the Potts antiferromagnet. The cavity method predicts that in addition to the k-colorability phase transition studied intensively in combinatorics, there exists a second phase transition called the condensation phase transition ( in Proc Natl Acad Sci 104:10318–10323, 2007). In fact, there is a conjecture as to the precise location of this phase transition in terms of a certain distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.
summary: The proof of combines the second moment arguments from Achlioptas and Naor @cite_26 and its enhancements from @cite_15 @cite_2 with the small subgraph conditioning'' method @cite_6 @cite_21 . More precisely, the key observation on which the proof of is based is that the fluctuations of @math can be attributed to the variations of the number of bounded length cycles in the random graph.