论文标题
Ramsey图和Erdős-Mckay的证明
Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
论文作者
论文摘要
$ n $ vertex图被称为$ c $ -ramsey，如果它没有大小$ c \ log_2 n $的集团或独立集（即，如果它具有接近最佳的Ramsey行为）。在本文中，我们研究了拉姆西图中的边缘统计数据，特别是在随机顶点子集中的边缘数量分布非常精确地控制边的分布。这汇集了两个正在进行的研究线：Ramsey图的“随机”特性的研究以及对独立随机变量低度多项式的小球概率的研究。 证明是通过程度序列的“加性结构”二分法进行的，涉及傅立叶分析，随机矩阵理论，布尔函数理论，概率组合术和低排名近似的各种不同工具。我们结果的后果之一是解决了旧的Erdős和McKay的旧猜想，ErdőS提供了他臭名昭著的货币奖品之一。
An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. This brings together two ongoing lines of research: the study of "random-like" properties of Ramsey graphs and the study of small-ball probabilities for low-degree polynomials of independent random variables. The proof proceeds via an "additive structure" dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős offered one of his notorious monetary prizes.
