Sharp thresholds for Ramsey properties

Ehud Friedgut

doi:10.1017/fms.2026.10178

Sharp thresholds for Ramsey properties

2026-02-27

0

PRE

AI

DOI：10.1017/fms.2026.10178

原文链接

原文求助

摘要

En 中文

本研究提出了一种统一框架，用于建立各种拉姆齐（Ramsey）性质的确切阈值结果。为此，我们将这些性质视为辅助超图的非可着色性。我们的主要技术成果给出了关于此类超图序列的充分条件，确保该非可着色性性质在由顶点随机子集诱导的子超图中具有确切阈值。此外，我们在若干感兴趣的情况下验证了这些条件。在图的拉姆齐理论的经典框架下，我们证明了“在r种颜色下对图H具有拉姆齐性质”这一属性在$G_{n,p}$中具有确切阈值，适用于所有$r \geqslant 2$以及包含所有完全图和环图的一类图。在算术框架下，我们还确立了与范德瓦尔登（van der Waerden）定理和舒尔（Schur）定理相对应的属性阈值的精确性，同样适用于任意数量的颜色。

Keyword:

RANDOM SUBSETS

GRAPHS

Sharp thresholds for Ramsey properties

摘要

期刊

机构

引用论文