Sparse random and pseudorandom graphs and graph Ramsey theory

稀疏随机和伪随机图以及图拉姆齐理论

• 批准号: 263484357
• 负责人: Professor Dr. Yury Person
• 金额: --
• 依托单位: Institut für Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2017-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/263484357?language=en
• 关键词: Sparse; random; pseudorandom; graphs; graph

Sparse random and pseudorandom graphs, and graph Ramsey theory as well are nowadays among the most important and influential topics investigated in extremal and probabilistic combinatorics, which have diverse connections to other areas of mathematics such as geometry, algebra and number theory and to theoretical computer science. The basic objects of study are graphs which are versatile models both for real life applications and for theoretical study. A typical problem concerning random graphs is what properties a graph sampled at random according to some probability distribution will possess? Pseudorandomness is a concept which tries to capture such properties in a deterministic way, which should make it more applicable to practical studies. Ramsey theory is a fascinating area whose main leitmotiv is a phenomenon observed throughout many branches of mathematics that every large enough structure must exhibit certain patterns, or put it in words of Theodore Motzkin: ``Complete disorder is impossible''. All topics have in common, that it often suffices to provide an algorithm or an embedding strategy which finds a smaller desired structure within some large structure. Our goal is to further explore these important topics by studying conditions under which one can find various spanning structures in random and pseudorandom graphs, and by investigating open problems of graph Ramsey theory.

稀疏随机图和伪随机图，以及图拉姆齐理论是当今极值和概率组合学中最重要和最有影响力的研究课题之一，与其他数学领域，如几何，代数和数论以及理论计算机科学有着不同的联系。图形是研究的基本对象，它是真实的生活应用和理论研究的通用模型。关于随机图的一个典型问题是根据某种概率分布随机抽样的图将具有什么性质？伪随机性是一个试图以确定性的方式捕获这些属性的概念，这应该使它更适用于实际研究。拉姆齐理论是一个迷人的领域，其主要主旨是在许多数学分支中观察到的一种现象，即每个足够大的结构都必须表现出某些模式，或者用西奥多·莫茨金的话来说：“完全无序是不可能的”。 所有主题都有一个共同点，即提供一种算法或嵌入策略，在某个大结构中找到一个较小的所需结构。我们的目标是进一步探讨这些重要课题的研究条件下，人们可以找到各种生成结构的随机和伪随机图，并通过调查开放的问题图拉姆齐理论。

项目成果

Spanning structures and universality in sparse hypergraphs

• DOI: 10.1002/rsa.20690
• 发表时间: 2015-04
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Olaf Parczyk;Y. Person

Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs

最小 Ramsey 3 均匀超图的最小度和代码

• DOI: 10.1016/j.endm.2015.06.005
• 发表时间: 2016
• 期刊: Electron. Notes Discret. Math.
• 作者: Dennis Clemens;Yury Person
• 通讯作者: Yury Person

SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS

随机超图中的对称和不对称拉姆齐性质

• DOI: 10.1017/fms.2017.22
• 发表时间: 2017
• 期刊: Forum of Mathematics, Sigma
• 作者: Luca Gugelmann;Rajko Nenadov;Yury Person;Nemanja Skorić;Angelika Steger;Henning Thomas
• 通讯作者: Henning Thomas