Pseudorandom Structures in Graphs and Combinatorics

数学中的许多组合问题是由计算机科学和网络设计中的大量实际应用所驱动的，例如划分、覆盖、布局、排序、路由、聚类、排序和度约束生成树。这些问题可以从研究物理结构(如光网络)或更抽象的结构(如社交网络)中产生。广义地说，PI试图通过利用顺序和随机性之间的二分法来更好地理解这些问题的核心数学结构(图、有向/定向图、超图、设计)。此外，这个项目将为本科生和硕士学生提供研究机会。国际和平研究所和他的合作者将探索拉姆齐理论和狄拉克/哈纳尔-塞梅尔迪理论的新领域。在拉姆齐理论中，我们被赋予了一个数学结构(比如集合的集合)，我们想知道在什么情况下，无论结构如何被划分为较小的部分，其中一个较小的部分肯定包含所需的子结构。狄拉克/哈纳尔-塞梅尔迪理论是关于保证宿主结构内存在某些跨度子结构的充分条件的研究。在这两种设置中，目标都是找到所需的子结构，而在这两种设置中，PI的目标都是开发实现这一点的一般方法。这些方法通常具有以下特点：要么宿主结构在某种意义上是高度有序的，要么具有伪随机性，这些属性可以被用来构建坚固的“脚手架”，该脚手架又可以用来构建所需的子结构。PI将建立在一系列工作的基础上，包括部分放松、规律性、扩展(和其他各种随机性衡量标准)和吸收。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many combinatorial problems in mathematics are motivated by numerous practical applications in computer science and network design such as partitioning, covering, packing, sequencing, routing, clustering, sorting, and degree constrained spanning trees. These problems can arise from studying either physical structures such as optical networks or more abstract structures such as social networks. Broadly speaking, the PI seeks to better understand the mathematical structures (graphs, directed/oriented graphs, hypergraphs, designs) at the heart of these problems by exploiting the dichotomy between order and randomness. Furthermore, this project will provide research opportunities for undergraduate and masters students.The PI and his collaborators will explore new territory in Ramsey theory and Dirac/Hajnal-Szemerédi theory. In Ramsey theory we are given a mathematical structure (say a collection of sets) and we want to know under what circumstances is it true that no matter how the structure is partitioned into smaller parts, one of those smaller parts must contain a desired substructure. Dirac/Hajnal-Szemerédi theory is about the study of sufficient conditions which guarantee the existence of certain spanning substructures within a host structure. In both settings the goal is to find a desired substructure and in both settings the PI's goal is to develop general methods for doing so. These methods will typically have the following flavor: either the host structure is highly ordered in some sense or else has psuedorandom properties which can be exploited to build a robust "scaffolding" which can in turn be used to construct the desired substructure. The PI will build upon a body of work including fractional relaxations, regularity, expansion (and various other measures of psuedorandomness), and absorption.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.