Exponential tails for factors and the chromatic number of random graphs
Abstract
The celebrated result of Johansson, Kahn and Vu determined the threshold order for clique factors in random graphs, and subsequent work identified the sharp threshold and the corresponding hitting-time phenomenon. In this paper we study the probability that there is no Kr-factor above the threshold and, more generally, the probability that the largest Kr-matching covers less than n−s vertices of G(n,p). For every fixed r≥3, throughout the range n−2/r(log n)1/binom r2≪ p≪ n−2/(r+1), n−s∈ rℤ, s=o(n), we prove ℙ(ϕrs(G(n,p))=0)=exp(−Θr ((s+1)μr(n,p)/n)), where ϕrs(G) is the number of Kr-matchings covering exactly n−s vertices and μr(n,p):=binom nrpbinom r2. The lower bound is given by s+1 vertices which lie in no copy of Kr. For the upper bound we develop an iterable one-root version of the Johansson--Kahn--Vu method. As a structural consequence, we show that the remainder of G(n,p) outside every maximal Kr-matching has an almost-perfect Kr−1-matching throughout the sparse clique window. Independently, we prove a central limit theorem for the maximum Kr-matching number. Combining these inputs and a structural theorem for r=2 from our earlier work, we prove a central limit theorem for the chromatic number of very dense random graphs: for every r≥2 and n−2/r(log n)1/binom r2≪ p≪ n−2/(r+1), (χ(G(n,1−p))−𝔼χ(G(n,1−p)))/(√(μr+1(n,p))/r)xrightarrowd𝒩(0,1), Var(χ(G(n,1−p))) ∼(μr+1(n,p))/r2. This settles the Surya--Warnke conjecture throughout the interior of every clique window with r≥2, strengthening its concentration prediction to a Gaussian limit with asymptotically exact variance.
Related
BibTeX
@misc{yan2026exponential,
title = {{Exponential tails for factors and the chromatic number of random graphs}},
author = {Zhifei Yan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12700},
eprint = {2609.12700},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12700},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exponential tails for factors and the chromatic number of random graphs
AU - Zhifei Yan
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.12700
UR - https://arxiv.org/abs/2609.12700
AB - The celebrated result of Johansson, Kahn and Vu determined the threshold order for clique factors in random graphs, and subsequent work identified the sharp threshold and the corresponding hitting-time phenomenon. In this paper we study the probability that there is no K_r-factor above the threshold and, more generally, the probability that the largest K_r-matching covers less than n−s vertices of G(n,p). For every fixed r≥3, throughout the range n^−2/r(log n)^1/binom r2≪ p≪ n^−2/(r+1), n−s∈ rℤ, s=o(n), we prove ℙ(ϕ_r^s(G(n,p))=0)=exp(−Θ_r ((s+1)μ_r(n,p)/n)), where ϕ_r^s(G) is the number of K_r-matchings covering exactly n−s vertices and μ_r(n,p):=binom nrp^binom r2. The lower bound is given by s+1 vertices which lie in no copy of K_r. For the upper bound we develop an iterable one-root version of the Johansson--Kahn--Vu method. As a structural consequence, we show that the remainder of G(n,p) outside every maximal K_r-matching has an almost-perfect K_r−1-matching throughout the sparse clique window. Independently, we prove a central limit theorem for the maximum K_r-matching number. Combining these inputs and a structural theorem for r=2 from our earlier work, we prove a central limit theorem for the chromatic number of very dense random graphs: for every r≥2 and n^−2/r(log n)^1/binom r2≪ p≪ n^−2/(r+1), (χ(G(n,1−p))−𝔼χ(G(n,1−p)))/(√(μ_r+1(n,p))/r)xrightarrowd𝒩(0,1), Var(χ(G(n,1−p))) ∼(μ_r+1(n,p))/r^2. This settles the Surya--Warnke conjecture throughout the interior of every clique window with r≥2, strengthening its concentration prediction to a Gaussian limit with asymptotically exact variance.
ER -