The Chromatic Number of Very Dense Random Graphs

The chromatic number of a very dense random graph $G(n,p)$, with p ≥ 1 - n⁻ᶜ 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(log n). They moreover proved their conjecture in the case n⁻² 1 - p = O(n⁻¹). In this paper, we study χ(G(n,p)) in the range n⁻¹log 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(n3/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⁻¹ log n 1 - p n-7/9.