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

作者：Fang Xiao^*

来源：Electronic Communications in Probability, 2015, 20(0): 1-6.

DOI：10.1214/ECP.v20-3707

• Stein's method
• normal approximation
• rate of convergence
• monochromatic edges

Let {G(n) : n >= 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 (2014) 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.

• 出版日期2015-3-5