Extremal Problems on Graphs and Hypergraphs

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

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.