Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests
Abstract
Given a graph sequence {Gn}n∈ℕ, denote by Tn the number of monochromatic edges when the vertices of Gn are independently colored red or blue with probabilities p and 1−p, respectively. We characterize the asymptotic normality of Tn, after centering and scaling to unit variance, in terms of subgraph (motif) counts and standardized moments. One of the highlights of our results is a {\it third moment phenomenon}: for every fixed p∈(0,1)backslash{1/2}, asymptotic normality holds if and only if the standardized third moment converges to zero. The more familiar {\it fourth moment condition}, which requires the standardized fourth moment to converge to $3$, gives an equivalent characterization except at the two exceptional probabilities p=1±1/√3/2. At these values, the standardized fourth moment converges to $3$ for every graph sequence with a diverging number of edges, even when Gaussian convergence fails. In contrast, in the balanced case p=1/2, the fourth moment condition characterizes asymptotic normality, while the third moment condition is insufficient. These results identify three distinct regimes for moment characterizations of Gaussian convergence, determined by the coloring probability. We further show that the third moment condition remains sufficient in the sparse regime, where p=pn → 0. As an application, we derive the limiting null distribution of two-sample statistics based on undirected K-nearest-neighbor graphs in the Poissonized setting, identifying sharp growth conditions on K for asymptotic normality.
Related
- Chaotic CLT using Poisson Fourth Moment Theorem and Graph Theory
- Universality of approximate message passing under a fourth-moment tail condition
- Fourth-Moment Strong Universality for Finite-Type Transpose-Correlated Random Matrices
- Sharp Fourth-Moment Wasserstein CLT Bounds
- When Unpaired Sets Support Shared-Corruption Calibration: Moment Geometry and Two-Sample Precision
BibTeX
@misc{athreya2026third,
title = {{Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests}},
author = {Siva Athreya and Bhaswar B. Bhattacharya and Yogesh Dahiya and Karambir Das and Spandan Ghoshal and Sourish Maniyar and Elizabeth Sara Roy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29215},
eprint = {2610.29215},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29215},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests
AU - Siva Athreya
AU - Bhaswar B. Bhattacharya
AU - Yogesh Dahiya
AU - Karambir Das
AU - Spandan Ghoshal
AU - Sourish Maniyar
AU - Elizabeth Sara Roy
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29215
UR - https://arxiv.org/abs/2610.29215
AB - Given a graph sequence {G_n}_n∈ℕ, denote by T_n the number of monochromatic edges when the vertices of G_n are independently colored red or blue with probabilities p and 1−p, respectively. We characterize the asymptotic normality of T_n, after centering and scaling to unit variance, in terms of subgraph (motif) counts and standardized moments. One of the highlights of our results is a {\it third moment phenomenon}: for every fixed p∈(0,1)backslash{1/2}, asymptotic normality holds if and only if the standardized third moment converges to zero. The more familiar {\it fourth moment condition}, which requires the standardized fourth moment to converge to $3$, gives an equivalent characterization except at the two exceptional probabilities p=1±1/√3/2. At these values, the standardized fourth moment converges to $3$ for every graph sequence with a diverging number of edges, even when Gaussian convergence fails. In contrast, in the balanced case p=1/2, the fourth moment condition characterizes asymptotic normality, while the third moment condition is insufficient. These results identify three distinct regimes for moment characterizations of Gaussian convergence, determined by the coloring probability. We further show that the third moment condition remains sufficient in the sparse regime, where p=p_n → 0. As an application, we derive the limiting null distribution of two-sample statistics based on undirected K-nearest-neighbor graphs in the Poissonized setting, identifying sharp growth conditions on K for asymptotic normality.
ER -