paper

A fourth moment phenomenon for asymptotic normality of monochromatic subgraphs

arXiv:2205.04285 · doi:10.1002/rsa.21166

Abstract

Given a graph sequence ${G_{n}}_{n \geq 1}$ and a simple connected subgraph $H$ , we denote by $T (H, G_{n})$ the number of monochromatic copies of $H$ in a uniformly random vertex coloring of $G_{n}$ with $c \geq 2$ colors. In this article, we prove a central limit theorem for $T (H, G_{n})$ with explicit error rates. The error rates arise from graph counts of collections formed by joining copies of $H$ that we call good joins. Counts of good joins are closely related to the fourth moment of a normalized version of $T (H, G_{n})$ , and that connection allows us to show a fourth moment phenomenon for the central limit theorem. Precisely, for $c \geq 30$ , we show that $T (H, G_{n})$ (appropriately centered and rescaled) converges in distribution to $N (0, 1)$ whenever its fourth moment converges to 3 (the fourth moment of the standard normal distribution). We show the convergence of the fourth moment is necessary to obtain a normal limit when $c \geq 2$ . The combination of these results implies that the fourth moment condition characterizes the limiting normal distribution of $T (H, G_{n})$ for all subgraphs $H$ , whenever $c \geq 30$ .

25 pages, 2 figures; comments welcome!