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

DOI10.1214/ECP.V20-3707MaRDI QIDQ2517246zbMATH OpenFDO

Authors Xiao Fang

Publication date 17 August 2015

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0509

zbMATH Keywords

monochromatic edgesnormal approximationrate of convergenceStein's method

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Central limit and other weak theorems (60F05)

Abstract: Let $G_n:ngeq1$ 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.

Recommendations

• Universal limit theorems in graph coloring problems with connections to extremal combinatorics
• Limit theorems for monochromatic stars
• scientific article; zbMATH DE number 17683
• Monochromatic subgraphs in randomly colored graphons
• A central limit theorem for decomposable random variables with applications to random graphs

Cited in

(9)

• Berry-Esseen bounds of normal and nonnormal approximation for unbounded exchangeable pairs
• Asymptotic distribution of Bernoulli quadratic forms
• Monochromatic subgraphs in randomly colored graphons
• Limit theorems for monochromatic stars
• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• Normal approximation and fourth moment theorems for monochromatic triangles
• Fluctuations of quadratic chaos
• Characterizing the fourth-moment phenomenon of monochromatic subgraph counts via influences
• Three-parameter approximations of sums of locally dependent random variables via Stein's method

This page was built for publication: A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2517246)