Normal approximation and fourth moment theorems for monochromatic triangles

DOI10.1002/RSA.21017MaRDI QIDQ6074673zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

birthday problemfourth-moment theoremgraph coloringmartingale central limit theoremrates of convergence

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: Given a graph sequence ${G_n}_{ngeq1}$ denote by $T_3(G_n)$ the number of monochromatic triangles in a uniformly random coloring of the vertices of $G_n$ with $cgeq2$ colors. This arises as a generalization of the birthday paradox, where $G_n$ corresponds to a friendship network and $T_3(G_n)$ counts the number of triples of friends with matching birthdays. In this paper we prove a central limit theorem (CLT) for $T_3(G_n)$ with explicit error rates. The proof involves constructing a martingale difference sequence by carefully ordering the vertices of $G_n$, based on a certain combinatorial score function, and using a quantitive 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 $cgeq5$. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any $cgeq2$, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of $T_3(G_n)$, whenever $cgeq5$. 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 Bhattacharya et al. (2017).

Recommendations

• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs
• Limit theorems for monochromatic stars
• Universal limit theorems in graph coloring problems with connections to extremal combinatorics
• A local central limit theorem for triangles in a random graph

Cites work

• A Bayesian peek into Feller volume. I
• A central limit theorem for generalized multilinear forms
• A central limit theorem for generalized quadratic forms
• A Class of Statistics with Asymptotically Normal Distribution
• A non-uniform birthday problem with applications to discrete logarithms
• A Poisson approximation for coloured graphs under exchangeability
• A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs
• Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process
• Central limit theorems for sequences of multiple stochastic integrals
• Collision times in multicolor urn models and sequential graph coloring with applications to discrete logarithms
• Collision-based Testers are Optimal for Uniformity and Closeness
• Exchangeable pairs and Poisson approximation
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• Hypergraphs, entropy, and inequalities
• Monochromatic subgraphs in randomly colored graphons
• Multicollision Attacks on Some Generalized Sequential Hash Functions
• Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests
• Normal approximations with Malliavin calculus. From Stein's method to universality
• On the Departure from Normality of a Certain Class of Martingales
• On the fourth moment condition for Rademacher chaos
• On the number of copies of one hypergraph in another
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• Quantitative de Jong theorems in any dimension
• Stein's method on Wiener chaos
• Testing closeness of discrete distributions
• The matching, birthday and the strong birthday problem: a contemporary review
• Universal limit theorems in graph coloring problems with connections to extremal combinatorics
• Universality of the mean-field for the Potts model

Cited in

(5)

• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• Fluctuations of quadratic chaos
• Characterizing the fourth-moment phenomenon of monochromatic subgraph counts via influences
• LDP for inhomogeneous U-statistics
• Joint Poisson convergence of monochromatic hyperedges in multiplex hypergraphs

This page was built for publication: Normal approximation and fourth moment theorems for monochromatic triangles

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