权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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问题特别有效。研究人员计划采用一些最新的数学工具，包括概率和多项式方法，以解决该领域的一些核心问题。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。