The Chromatic Number of Very Dense Random Graphs

The chromatic number of a very dense random graph G (n, p), with p 1 - n^-c for some constant c > 0, was first studied by Surya and Warnke, who conjectured that the typical deviation of (G (n, p) ) from its mean is of order ᵣ, % fluctuates by about (ᵣ), where ᵣ is the expected number of independent sets of size r, and r is maximal such that ᵣ > 1, except when ᵣ = O (n). They moreover proved their conjecture in the case n^-2 1 - p = O (n^-1). In this paper, we study (G (n, p) ) in the range n^-1 n 1 - p n^-2/3, that is, when the largest independent set of G (n, p) is typically of size 3. We prove in this case that (G (n, p) ) is concentrated on some interval of length O (₃), %O (n^3/2 (1-p) ^3/2) =O (₃) with high probability. Moreover for a big family of p (n), there is and for sufficiently `smooth' functions p = p (n), that there are infinitely many values of n such that (G (n, p) ) is not concentrated on any interval of size o (₃). We also show that (G (n, p) ) satisfies a central limit theorem in the range n^-1 n 1 - p n^-7/9.