Ramsey-type problems in random and in randomly perturbed discrete structures, and their sharp thresholds

随机和随机扰动离散结构中的拉姆齐型问题及其锐阈值

• 批准号: 447645533
• 负责人: Professor Dr. Yury Person
• 金额: --
• 依托单位: Institut für Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/447645533?language=en
• 关键词: Ramsey; type; problems; random; randomly

The study of random discrete structures and their interplay with deterministic counterparts is an active stream of research within extremal and probabilistic combinatorics. It has been observed by several researchers that the combination of a deterministic object with a random structure often leads to much better results. Bohman, Frieze and Martin introduced in 2001 the randomly perturbed graph model and proved that adding to a graph of small linear degree linearly many edges at random results very likely in a Hamiltonian graph. In the recent few years the study of randomly perturbed models has been extended to hypergraphs and sets of integers and is now an active research direction with many interesting insights. The purpose of this project is to further advance this area, especially focusing on Ramsey-type problems around randomly perturbed discrete structures (graphs, hypergraphs, sets of integers) and their relation to the corresponding statements in purely random models. Moreover, the phenomenon of the so-called sharp thresholds (where the structure undergoes a dramatic change of its characteristic properties) should be studied and Ramsey-type problems appear to be a challenging testbed.

随机离散结构及其与确定性结构的相互作用的研究是极值和概率组合学中一个活跃的研究方向。一些研究人员已经观察到，确定性对象与随机结构的组合通常会导致更好的结果。Bohman，Frieze和Martin在2001年引入了随机扰动图模型，证明了在一个小线性度的图上随机添加多条边很可能会得到一个Hamilton图。最近几年，随机扰动模型的研究已经扩展到超图和整数集，现在是一个活跃的研究方向，有许多有趣的见解。该项目的目的是进一步推进这一领域，特别是关注随机扰动离散结构（图，超图，整数集）及其与纯随机模型中相应语句的关系的拉姆齐型问题。此外，应该研究所谓的尖锐阈值（结构经历其特征性质的急剧变化）的现象，并且Ramsey型问题似乎是一个具有挑战性的测试平台。