A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs

Xiao Fang

paper

A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs

arXiv:1408.0509

Abstract

Let ${G_{n} : n \geq 1}$ be a sequence of simple graphs. Suppose $G_{n}$ has $m_{n}$ edges and each vertex of $G_{n}$ is colored independently and uniformly at random with $c_{n}$ colors. Recently, Bhattacharya, Diaconis and Mukherjee (2013) proved universal limit theorems for the number of monochromatic edges in $G_{n}$ . Their proof was by the method of moments, and therefore was not able to produce rates of convergence. By a non-trivial application of Stein's method, we prove that there exists a universal error bound for their central limit theorem. The error bound depends only on $m_{n}$ and $c_{n}$ , regardless of the graph structure.

6 pages