Random and pseudorandom structures and their applications

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

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.