Pseudorandom Structures in Graphs and Combinatorics

数学中的许多组合问题是由计算机科学和网络设计中的许多实际应用驱动的，例如分区、覆盖、打包、排序、路由、聚类、排序和程度约束生成树。这些问题可以从研究物理结构（如光网络）或更抽象的结构（如社会网络）中产生。广义地说，PI试图通过利用有序和随机性之间的二分法，更好地理解这些问题核心的数学结构（图、有向/有向图、超图、设计）。此外，本项目将为本科生和硕士生提供研究机会。PI和他的合作者将探索Ramsey理论和Dirac/ hajnal - szemersamedi理论的新领域。在拉姆齐理论中，我们给定一个数学结构（比如一个集合的集合），我们想知道在什么情况下，不管这个结构如何被分割成更小的部分，其中一个更小的部分必须包含一个期望的子结构。Dirac/ hajnal - szemersamedi理论研究的是保证主结构中存在某些跨越子结构的充分条件。在这两种情况下，目标都是找到所需的子结构，在这两种情况下，PI的目标都是开发这样做的通用方法。这些方法通常具有以下特点：宿主结构在某种意义上是高度有序的，或者具有可用于构建健壮的“脚手架”的伪随机属性，该“脚手架”可依次用于构建所需的子结构。PI将建立在一系列工作的基础上，包括分数松弛、规律性、膨胀（以及其他各种伪随机性的测量）和吸收。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.