Extremal Problems on Graphs and Hypergraphs

图和超图的极值问题

• 批准号: 1855542
• 负责人: Tao Jiang
• 金额: $ 10.04万
• 依托单位: Miami University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1855542&HistoricalAwards=false
• 关键词: Extremal; Problems; Graphs; Hypergraphs

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.

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

项目成果

Linear cycles of consecutive lengths

• DOI: 10.1016/j.jctb.2023.06.002
• 发表时间: 2020-06
• 期刊: J. Comb. Theory B
• 作者: T. Jiang;Jie Ma;Liana Yepremyan

Tree-Degenerate Graphs and Nested Dependent Random Choice

树退化图和嵌套相关随机选择

• DOI: 10.1137/22m1483554
• 发表时间: 2023
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Jiang, Tao;Longbrake, Sean
• 通讯作者: Longbrake, Sean

Turán Numbers of Bipartite Subdivisions

二分细分的图兰数

• DOI: 10.1137/19m1265442
• 发表时间: 2020
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Jiang, Tao;Qiu, Yu
• 通讯作者: Qiu, Yu

Partitioning ordered hypergraphs

划分有序超图

• DOI: 10.1016/j.jcta.2020.105300
• 发表时间: 2021
• 期刊: Series A
• 作者: Füredi, Zoltán;Jiang, Tao;Kostochka, Alexandr;Mubayi, Dhruv;Verstraëte, Jacques
• 通讯作者: Verstraëte, Jacques