We derive normal approximation bounds in the Kolmogorov distance for sums of discrete multiple integrals and $U$-statistics made of independent Bernoulli random variables. Such bounds are applied to normal approximation for the renormalized subgraphs counts in the Erd{ \H o}s-R\'enyi random graph. This approach completely solves a long-standing conjecture in the general setting of arbitrary graph counting, while recovering and improving recent results derived for triangles as well as results using the Wasserstein distance.
Categories: math.PR