FRG: Collaborative Research: Extremal Combinatorics and Flag Algebras

FRG：协作研究：极值组合学和标志代数

• 批准号: 2152488
• 负责人: Jozsef Balog
• 金额: $ 50.86万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2152488&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Extremal; Combinatorics

In extremal combinatorics one aims to find and characterize optimal members of a given class of mathematical objects. Those extremal objects often have unique properties and structures, giving insights in many mathematical fields. Over the last twenty years, several new techniques, many using the assistance of computers, have been extraordinarily successful in studying extremal objects. One of the recent powerful methods is based on the theory of flag algebras. This method enables researchers to translate extremal combinatorics questions into instances of semidefinite programs, which can then be explored with the help of a computer and academic as well as commercial software. This translation has led to recent breakthroughs on longstanding open questions. The method is versatile and can be applied in various settings such as graphs, hypergraphs, permutations, oriented graphs, point sets, embedded graphs, and phylogenetic trees. The aim of this focused research group is to resolve three prominent types of open questions by Erdős, Turán, and Zarankiewicz using these techniques.The three types of questions to be studied share the general flavor of generalized Turán problems, and solving them would have far reaching consequences. The first type are extremal hypergraph questions, the second type concerns finding maximum cuts in graphs with certain properties, and the third type are questions related to the crossing number of graphs. For all three, the use of flag algebras has recently led to significant progress but not to full solutions. This project will combine the expertise of the investigators with a concentrated effort and further method development to resolve these open questions. It is planned to find connections to more traditional methods such as the stability method and linear algebraic methods. A substantial number of students and early-career researchers will be trained and supported at the three institutions, and several focused workshops are planned.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.

在极值组合学中，人们的目标是找到并表征给定类别的数学对象的最佳成员，这些极值对象通常具有独特的属性和结构，在过去的二十年中，出现了多种新技术，其中许多都使用了辅助技术。计算机在研究极值对象方面取得了巨大的成功，其中一种基于标志代数理论的方法使研究人员能够将极值组合问题转化为半定程序的实例。在计算机和学术以及商业软件的帮助下进行探索，这种翻译在长期悬而未决的问题上取得了突破，该方法是通用的，可以应用于各种设置，例如图、超图、排列、有向图、这个重点研究小组的目标是利用这些技术解决 Erdős、Turán 和 Zarankiewicz 提出的三种主要类型的开放性问题。要研究的三种类型的问题是共享的。广义图兰问题的一般特征，解决它们将产生深远的影响，第一类是极值超图问题，第二类涉及寻找具有某些属性的图中的最大割，第三类是与交叉数相关的问题。对于这三个问题，标志代数的使用最近取得了重大进展，但尚未取得完整的解决方案。该项目计划将研究人员的专业知识与集中的努力和进一步的方法开发结合起来，以解决这些悬而未决的问题。找到与更传统方法的联系，例如稳定性方法和线性代数方法的大量学生和早期职业研究人员将在这三个机构接受培训和支持，并计划举办一些重点研讨会。该奖项反映了 NSF 的法定使命，并通过评估被认为值得支持。利用基金会的智力优势和更广泛的影响审查标准。

项目成果

The Spectrum of Triangle-Free Graphs

无三角形图的谱

• DOI: 10.1137/22m150767x
• 发表时间: 2023-06
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Balogh, József;Clemen, Felix Christian;Lidický, Bernard;Norin, Sergey;Volec, Jan
• 通讯作者: Volec, Jan