Global and Local Properties of Discrete Structures

组合结构理论与数学的几个领域密切相关，包括代数，逻辑，数论和概率，以及其他领域，如信息论，编码理论，理论计算机科学和统计物理。研究随机和伪随机结构已成为一个重要的研究课题，特别是因为研究结果和开发的技术被证明是有用的大型网络的重要应用的研究。最近发现的稀疏组合结构和枚举问题之间的联系产生了一些需要进一步研究的深入结果。该研究项目的重点是了解密集结构的重要属性的鲁棒性，并测试它们是否被随机稀疏子结构继承，目标是发展一个统一的理论。该项目将涉及通过参与研究来培训研究生，预计其中一些结果将被整合到研究生培训课程中。组合学在过去二十年中的一个中心焦点是引入和证明极值图论、拉姆齐理论和加法组合学中的各种著名定理的随机类似物。最近，所谓的容器方法被开发出来，它被证明是有用的攻击这些问题和许多其他问题。该项目的一个研究方向将集中在该方法的应用上，预计这种探索将导致新的令人兴奋的问题和方向。 本文主要研究了以下几个方面的问题：（1）稀疏结构中的极值问题;（2）稀疏随机图和伪随机图的子图嵌入问题;（3）旗代数的应用;以及（4）该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查进行评估，被认为值得支持的搜索.

The theory of combinatorial structures is closely related to several areas of mathematics, including algebra, logic, number theory, and probability, as well as to other fields such as information theory, coding theory, theoretical computer science, and statistical physics. Investigating random and pseudo-random structures has become an important research topic, particularly because the results and the techniques developed proved to be useful in the study of large networks in important applications. A recently-discovered connection between sparse combinatorial structures and enumeration problems yielded several deep results that call for further study. This research project focuses on understanding the robustness of important properties of dense structures and testing whether they are inherited by random sparse substructures, with the goal of developing a unified theory. The project will involve training of graduate students through involvement in the research, and it is anticipated that some of the results will be integrated into courses for graduate student training.A central focus of combinatorics over the past twenty years has been the introduction and proof of various random analogues of well-known theorems in extremal graph theory, Ramsey theory, and additive combinatorics. Recently, the so-called container method was developed, which proved to be useful to attack these questions and many others. One direction of research in this project will focus on applications of the method, and it is expected that this exploration will lead to new exciting questions and directions. In particular, the following related areas are to be investigated: (1) extremal questions in sparse structures; (2) embedding in subgraphs of sparse random and pseudo-random graphs; (3) applications of flag algebras; and (4) problems in bootstrap percolation.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.