Extremal problems for sparse hypergraphs and graphs

稀疏超图和图的极值问题

• 批准号: 1400249
• 负责人: Tao Jiang
• 金额: $ 13.32万
• 依托单位: Miami University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-15 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1400249&HistoricalAwards=false
• 关键词: Extremal; problems; sparse; hypergraphs; graphs

Extremal combinatorics is a fast developing subarea within modern mathematics that investigates extremal values of useful parameters of discrete networks/systems. Its study has far reaching applications in computer science, information theory, engineering, or even social science. The project focuses on the following central problem in extremal combinatorics: how large/dense can a discrete system be before certain substructures are set to emerge? Such a study is critical to our analysis of discrete networks. In the analysis of discrete networks, graphs and hypergraphs are two of the main mathematical models. In the past several decades, powerful tools have been developed in the study of graphs and hypergraphs, especially for those that are dense. However, in general, there is a lack of effective tools for sparse graphs and hypergraphs. The project aims at developing some useful tools for the study of extremal problems for sparse graphs and hypergraphs via a study of several specific problems.The first objective of this project is to adapt tools from classical extremely set theory for general sparse hypergraphs. The PI and collaborators have recently applied tools from classical extremal set theory such as the delta system method and shadow analysis to solve Turan type problems for some general sparse hypergraphs. The PI will exploit this connection and look to adapt and develop tools for a more widely applicable setting. A second objective is to investigate how the shadow structure of a sparse hypergraph affects its Turan and Ramsey properties. One particular problem in this direction is to study Turan and Ramsey problems for hypergraphs that are obtained from graphs through expanding edges into hyperedges via new vertices. Another problem of particular emphasis is the Turan problem for hyperforests on which the PI and collaborators and other groups have made substantial recent progress, generalizing several classic results. A third objective is to combine existing tools and to develop new tools for the Turan problem for sparse bipartite graphs. One particular plan is to explore the combination of the expansion method with supersaturation of subgraphs and dependent random choice on sparse bipartite graphs. The PI and collaborators have had some recent success in this direction and will continue such an investigation. There is also an important educational component to this project. The PI has been actively involving masters students in research projects and will continue such endeavors on this project.

极值组合学是现代数学中一个快速发展的分支，研究离散网络/系统的有用参数的极值。它的研究在计算机科学、信息论、工程甚至社会科学中都有着深远的应用。该项目的重点是极值组合学中的以下中心问题：在某些子结构出现之前，离散系统可以有多大/密集？ 这样的研究对我们分析离散网络至关重要。在离散网络分析中，图和超图是两种主要的数学模型。在过去的几十年里，在图和超图的研究中，特别是对于那些稠密的图和超图，已经开发了强大的工具。然而，一般来说，缺乏有效的工具，稀疏图和超图。该项目旨在通过对几个具体问题的研究，为稀疏图和超图的极值问题的研究开发一些有用的工具。该项目的第一个目标是将经典极集理论的工具应用于一般稀疏超图。PI和合作者最近应用经典极值集理论的工具，如delta系统方法和阴影分析，解决一些一般稀疏超图的Turan型问题。PI将利用这一联系，并寻求适应和开发更广泛适用的工具。 第二个目标是研究稀疏超图的阴影结构如何影响其Turan和Ramsey性质。 在这个方向上的一个特殊问题是研究超图的Turan和Ramsey问题，这些超图是通过将边通过新的顶点扩展为超边而得到的。 另一个特别强调的问题是超级森林的图兰问题，PI和合作者以及其他小组最近取得了重大进展，推广了几个经典结果。第三个目标是联合收割机现有的工具，并开发新的工具，稀疏二分图的图兰问题。一个特别的计划是探索扩展方法与子图的过饱和和稀疏二分图上的依赖随机选择的组合。PI和合作者最近在这方面取得了一些成功，并将继续进行此类调查。 该项目还有一个重要的教育组成部分。PI一直积极参与研究项目的硕士生，并将继续在这个项目上这样的努力。

项目成果

Tight paths in convex geometric hypergraphs

凸几何超图中的紧路径

• DOI: 10.19086/aic.12044
• 发表时间: 2020
• 期刊: Advances in Combinatorics
• 作者: Mubayi, Dhruv;Füredi, Zoltán;Verstraëte, Jacques;Kostochka, Alexandr;Jiang, Tao
• 通讯作者: Jiang, Tao