ANTI-CONCENTRATION FOR SUBGRAPH COUNTS IN RANDOM GRAPHS

Fix a graph H and some p is an element of (0, 1), and let X-H be the number of copies of H in a random graph G(n, p). Random variables of this form have been intensively studied since the foundational work of Erdos and Renyi. There has been a great deal of progress over the years on the large-scale behaviour of X-H, but the more challenging problem of understanding the small-ball probabilities has remained poorly understood until now. More precisely, how likely can it be that X-H falls in some small interval or is equal to some particular value? In this paper, we prove the almost-optimal result that if H is connected then for any x is an element of N we have Pr(X-H = x) <= n(1- v(H)+ o(1)). Our proof proceeds by iteratively breaking X-H into different components which fluctuate at "different scales", and relies on a new anti-concentration inequality for random vectors that behave "almost linearly."