Turan-Type Extremal Problems and Applications

在这个研究项目中研究的问题是一个被广泛称为极值组合的数学领域的核心，它开发了分类和分析数学结构的工具，其中某些子结构是禁止的。一个典型的问题要求对不包含某些子图的最大边数的图进行分类。这些问题背后的数学理论是许多数学领域的基础，包括组合数论和几何。应用于不同的科学领域，包括理论计算机科学、编码和密码学、算法复杂性以及其他数学领域。极值结构在纠错码的构造中特别有价值。该项目探索了理论的创新方法，即将原始问题嵌入几何设置中，并使用强加的几何来获取额外信息。该项目包括通过研究生参与研究来培训他们。本项目涉及组合学的研究，重点是图兰型极值问题及其应用。通过探索纯图兰型问题与其他数学领域之间的联系，该项目旨在为解决一些重要的开放性问题提供新的见解。这种联系导致了最近的成功，例如多项式方法突破了数学帽集问题，这是一个图兰型问题，与两个方阵乘法的复杂性密切相关，这是许多实际应用的核心。在这个项目中，我们探索了一些新的方法，即我们在几何设置中嵌入图兰型问题，然后使用强加的几何来获取有关原始问题的信息。这种方法在最近的研究中对某些著名的超图图兰问题特别有效。研究人员计划使用一些最新的数学工具，包括概率和多项式方法，来解决该领域的一些核心问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The questions under study in this research project are central to an area of mathematics known broadly as extremal combinatorics, which develops tools to classify and analyze mathematical structures in which certain substructures are forbidden. A typical question asks for the classification of graphs with a maximum number of edges that do not contain certain subgraphs. The mathematical theory behind such questions is at the foundation of many areas of mathematics, including combinatorial number theory and geometry. Applications are found in diverse areas of science, including theoretical computer science, coding and cryptography, algorithmic complexity, as well as other areas of mathematics. Extremal structures are particularly valuable in the construction of error-correcting codes. This project explores innovative approaches to the theory, whereby an original question is embedded in a geometric setting and the imposed geometry is used to obtain additional information. The project includes training of graduate students through their involvement in the research.This project concerns research in combinatorics, focusing on Turan-type extremal problems and applications. By exploring the connection between pure Turan-type problems and other areas of mathematics, the project aims for new insights to solve some important open problems. Such connections have resulted in recent success, such as the polynomial method for breakthroughs on the mathematical cap set problem, a Turan-type problem closely related to the complexity of multiplication of two square matrices, which is at the heart of many practical applications. In this project, some new approaches are explored, whereby we embed a Turan type problem in a geometric setting, and then use the imposed geometry to obtain information regarding the original problem. This approach has been particularly effective in recent work for certain well-known hypergraph Turan problems. The researcher plans to employ some of the most recent mathematical tools, including probabilistic and polynomial methods, to solve some central problems in the area.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.