论文标题
单色三角形的正常近似值和第四刻定理
Normal Approximation and Fourth Moment Theorems for Monochromatic Triangles
论文作者
论文摘要
给定图形序列$ \ {g_n \} _ {n \ geq 1} $用$ t_3（g_n）$表示单色三角形的数量，以$ g_n $的顶点的均匀随机着色，带有$ c \ geq 2 $。这是作为生日悖论的概括而产生的，其中$ g_n $对应于友谊网络，而$ t_3（g_n）$都计算出与生日相匹配的朋友的数量。在本文中，我们证明了$ t_3（g_n）$具有明确错误率的中心限制定理（CLT）。证明涉及通过根据某个组合分数函数仔细订购$ g_n $的顶点来构建Martingale差异顺序，并使用Martingale CLT的定量版本。然后，我们将这个错误术语与众所周知的第四刻现象相关联，有趣的是，它仅在颜色数量$ c \ geq 5 $时才保持。我们还表明，对于任何$ c \ geq 2 $获得高斯限制，第四刻的融合是必要的，这与上述结果一样，这意味着第四兆条件是每当$ c \ geq 5 $中的限制正态分布（g_n）$。最后，为了说明我们方法的承诺，我们包括单色边数数量的CLT的替代证明，该证明为Bhattacharya等人获得的结果提供了定量率。 （2017）。
Given a graph sequence $\{G_n\}_{n \geq 1}$ denote by $T_3(G_n)$ the number of monochromatic triangles in a uniformly random coloring of the vertices of $G_n$ with $c \geq 2$ 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 $c \geq 5$. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any $c \geq 2$, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of $T_3(G_n)$, whenever $c \geq 5$. 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).
