Turan-Type Extremal Problems and Applications

图兰型极值问题及其应用

基本信息

批准号：
1800832
负责人：
Jacques Verstraete
金额：
$ 19.5万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2021-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1800832&HistoricalAwards=false
关键词：
Turan Type Extremal Problems 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.

该研究项目中所研究的问题是数学领域的核心，广泛地称为“极端组合”，该领域开发了对禁止某些子结构的数学结构进行分类和分析的工具。一个典型的问题要求将不包含某些子图的边缘数量数量的图形分类。这些问题背后的数学理论是数学领域的基础，包括组合数理论和几何形状。在科学的不同领域中发现了应用，包括理论计算机科学，编码和加密，算法复杂性以及其他数学领域。极端结构在构建错误校正代码中特别有价值。该项目探讨了该理论的创新方法，从而将原始问题嵌入到几何环境中，并使用施加的几何形状来获取其他信息。该项目包括通过参与研究的研究生培训。该项目涉及组合学研究，重点关注Turan型极端问题和应用。通过探索纯Turan型问题与其他数学领域之间的联系，该项目旨在寻求新的见解来解决一些重要的开放问题。这种连接导致了最近的成功，例如在数学上限集问题上进行突破的多项式方法，这是与两个正方形矩阵的乘法复杂性密切相关的Turan型问题，这是许多实际应用的核心。在该项目中，探索了一些新方法，从而将Turan型问题嵌入几何环境中，然后使用施加的几何形状获取有关原始问题的信息。对于某些众所周知的HyperGraph Turan问题，这种方法在最近的工作中特别有效。研究人员计划采用一些最新的数学工具，包括概率和多项式方法，以解决该地区的一些核心问题。该奖项反映了NSF的法定任务，并认为值得通过基金会的知识分子优点和更广泛的影响来通过评估来进行评估。