Extremal Problems on Graphs and Hypergraphs

快速的技术发展使我们有必要努力理解大型复杂的网络，如互联网。在这个项目中研究的问题是一个普遍的主题：当一个网络/系统足够密集时，什么样的局部子结构会被迫出现？找到这些问题的解决方案将使我们能够更有效地在大型网络上执行任务，并将在计算机科学、编码理论和信息论等领域产生应用。所研究的具体问题属于极值组合学的范畴：研究各种局部约束下的离散数学对象。近几十年来，极值组合学得到了显著的发展，这要归功于应用中出现的实际问题，以及来自其他数学分支（如概率论、代数、几何和分析）的思想和工具的注入。对于密集系统，一种被称为正则性方法的成熟方法允许人们将系统划分为行为良好的均匀块。然而，对于稀疏系统，不存在这种普遍适用的工具。本项目旨在通过对子结构过饱和的研究和寻找稀疏正则性方法的有效应用，为稀疏系统开发更通用的工具。项目中所追求的问题适合PI积极参与的研究生和早期职业数学家。该项目侧重于图兰类型的极端问题，其中我们想要确定当某些子配置被禁止时系统的密度如何。这些问题是极值组合学发展的核心。对于图，当禁止子图是非二部的（即非2色的）时，问题得到了很好的解决。当禁止子图为二部时，由于主图的稀疏性，问题变得更加棘手。发展这一重要领域的许多努力是由Erdos和Simonovits的几个一般猜想所驱动的，特别是两个所谓的图兰指数猜想。在最近的一项突破中，Bukh和Conlon解决了两个猜想中的一个，而关于单二部图的猜想则是完全开放的。PI和他的合作者通过所谓的过饱和方法在第二个猜想上取得了初步进展。其思想是在主图过于密集时，利用某些子图的过饱和和主图的局部约束来构建禁止子图。该方法具有发展成为解决稀疏环境下图兰型极值问题的通用工具的潜力。PI希望充分发展这种方法，并在图兰指数猜想上取得进一步进展。本课题的另一个目的是寻找将稀疏正则性方法应用于确定性图兰型问题的有效方法。PI将研究的第三组问题是图和超图中关于循环的极值问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Fast technological developments have necessitated our efforts to understand large complex networks, such as the internet. Questions studied in this project are of the general theme: what kind of local substructures are forced to emerge when a network/system is dense enough? Finding solutions to these problems will allow us to perform tasks on large networks more efficiently and will yield applications in areas such as computer science, coding theory, and information theory. The specific problems studied fall into the realm of extremal combinatorics: a study of discrete mathematical objects under various local constraints. In recent decades, extremal combinatorics has witnessed significant developments thanks to both practical problems arising from applications and an infusion of ideas and tools from various other branches of mathematics such as probability, algebra, geometry and analysis. For dense systems, a well-developed method called the regularity method allows one to partition a system into well-behaved uniform pieces. However, for sparser systems, no such universally applicable tools exist. This project aims at developing more universal tools for sparse systems through the study of supersaturation of substructures and through finding effective applications of the sparse regularity method. The problems pursued in the project are suitable for graduate students and early career mathematicians whom the PI will actively engage.The project focuses on Turan type extremal problems, in which we want to determine how dense a system can be when certain sub-configurations are forbidden. These problems are central to the development of extremal combinatorics. For graphs, the problem is well-solved when the forbidden subgraph is non-bipartite (i.e. not 2-colorable). When the forbidden subgraph is bipartite, the problem becomes more intractable due to the host graph being sparse. Much effort in developing this important field is driven by several general conjectures of Erdos and Simonovits, particularly the two so-called Turan exponents conjectures. In a recent breakthrough, Bukh and Conlon solved one of the two conjectures, while the one for single bipartite graphs is wide-open. The PI and his collaborators made initial progress on this second conjecture through the so-called supersaturation approach. The idea is to use supersaturation of certain subgraphs together with local constraints of the host graph to build the forbidden subgraph once the host graph is too dense. This method has the potential of being developed into a general tool to tackle Turan type extremal problems in the sparse setting. The PI looks to fully develop this method and make further progress on the Turan exponent conjecture. Another aim of the project is to find effective ways to apply the sparse regularity method for deterministic Turan type problems in the sparse setting. A third set of problems the PI will pursue are extremal problems on cycles in graphs and hypergraphs.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.