Normal approximation and fourth moment theorems for monochromatic triangles. Issue 1 (17th May 2021)

• Record Type: Journal Article
• Authors: Bhattacharya, Bhaswar B.; Fang, Xiao; Yan, Han
• Is Part Of: Random structures & algorithms. Volume 60:Issue 1(2022)
• Page Start: 25
• Page End: 53
• Publication Date: 2021-05-17
• Subjects: birthday problem -- fourth‐moment theorem -- graph coloring -- martingale central limit theorem -- rates of convergence; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21017
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Given a graph sequence { G n } 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].