Normal approximation and fourth moment theorems for monochromatic triangles

Given a graph sequence {Gn}n >= 1 denote by T-3(G(n)) the number of monochromatic triangles in a uniformly random coloring of the vertices of G(n) with c >= 2 colors. In this paper we prove a central limit theorem (CLT) for T-3(G(n)) with explicit error rates, using a quantitative version of the martingale CLT. We then relate this error term to the well-known fourth-moment phenomenon, which, interestingly, holds only when the number of colors satisfies c >= 5. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any c >= 2, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of T-3(G(n)), whenever c >= 5. Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in [7].