Random and pseudorandom structures and their applications

随机和伪随机结构及其应用

• 批准号: 1362326
• 负责人: Yufei Zhao
• 金额: $ 13万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1362326&HistoricalAwards=false
• 关键词: Random; pseudorandom; structures; their; applications

The study of randomly constructed objects, such as random graphs, had immense impact on discrete mathematics and related fields over the past fifty years. For example, the tools developed to solve open problems in the theory, now famously named the probabilistic method, provided a new way of thinking and serves as a link between combinatorics, analysis, number theory and geometry. Also, the random objects themselves found applications in fields such as theoretical computer science and statistical physics. As an instance, they are utilized as a theoretical framework for studying massive networks (e.g., internet, social networks, and neural networks) which are becoming of growing importance. Yet despite the great amount of work devoted to this topic over the past fifty years, many interesting unresolved questions, especially regarding the global structure of random graphs, still remain to be answered. Furthermore, the successful development of the theory of random graphs served as a natural motivation for the study of pseudorandom graphs, which can be informally described as deterministic graphs that behave like truely random graphs. Problems in the theory of pseudorandom graphs often are motivated by practical problems and are connected to deep philosophical questions such as, "Can we imitate true randomness?".In this project, the PI plans to study open problems in the field of random and pseudorandom graphs to further develop the theory and deepen the understanding of these fasicnating objects. The main problems that the PI plans to focus on are the conjectures of Krivelevich and Sudakov on Hamiltonicity of pseudorandom graphs, and of Kahn and Kalai on the threshold of appearance of fixed spanning subgraphs in binomial random graphs. These problems were chosen because they are representative problems that address the challenges that we are currently facing in understanding the global properties of random and pseudorandom graphs. The PI also plans to study related problems in combinatorics such as Sidorenko's conjecture, explicit construction of Ramsey graphs, and Turan-type problems in hypercubes.

在过去的五十年里，对随机构造对象（如随机图）的研究对离散数学及其相关领域产生了巨大的影响。例如，为解决理论中的开放问题而开发的工具，现在被称为概率方法，提供了一种新的思维方式，并成为组合学，分析，数论和几何之间的联系。此外，随机对象本身在理论计算机科学和统计物理等领域也有应用。例如，它们被用作研究大规模网络的理论框架（例如，因特网、社交网络和神经网络），其正变得越来越重要。然而，尽管在过去的50年里，大量的工作致力于这一主题，许多有趣的未解决的问题，特别是关于随机图的全球结构，仍然有待回答。此外，随机图理论的成功发展为伪随机图的研究提供了自然的动力，伪随机图可以被非正式地描述为行为像真正随机图的确定性图。伪随机图理论中的问题通常是由实际问题引起的，并且与深层次的哲学问题有关，例如，“我们能模仿真正的随机性吗？在这个项目中，PI计划研究随机和伪随机图领域的开放问题，以进一步发展理论并加深对这些fasicnating对象的理解。PI计划关注的主要问题是Krivelevich和Sudakov关于伪随机图的Hamilton性的理论，以及Kahn和Kalai关于二项式随机图中固定生成子图出现的阈值的理论。选择这些问题是因为它们是解决我们目前在理解随机和伪随机图的全局特性方面所面临的挑战的代表性问题。PI还计划研究组合学中的相关问题，如Sidorenko猜想，Ramsey图的显式构造和超立方体中的Turan型问题。

项目成果

Efficient arithmetic regularity and removal lemmas for induced bipartite patterns.

诱导二分模式的高效算术正则性和去除引理。

• DOI: 10.19086/da
• 发表时间: 2019
• 期刊: Discrete analysis
• 影响因子: 1.1
• 作者: Alon, Noga;Fox, Jacob;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Impartial Digraphs

公正有向图

• DOI: 10.1007/s00493-020-4280-0
• 发表时间: 2020
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Zhao, Yufei;Zhou, Yunkun
• 通讯作者: Zhou, Yunkun

Hypergraph expanders of all uniformities from Cayley graphs

凯莱图所有均匀性的超图扩展器

• DOI: 10.1112/plms.12371
• 发表时间: 2020
• 期刊: Proceedings of the London Mathematical Society
• 影响因子: 1.8
• 作者: Conlon, David;Tidor, Jonathan;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Upper Tail Large Deviations for Arithmetic Progressions in a Random Set

随机集中算术级数的上尾大偏差

• DOI: 10.1093/imrn/rny022
• 发表时间: 2018
• 期刊: International Mathematics Research Notices
• 影响因子: 1
• 作者: Bhattacharya, Bhaswar B;Ganguly, Shirshendu;Shao, Xuancheng;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Exponential improvements for superball packing upper bounds

• DOI: 10.1016/j.aim.2020.107056
• 发表时间: 2019-04
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: A. Sah;Mehtaab Sawhney;David Stoner;Yufei Zhao