Collaborative Research: Flag Algebra and Its Applications

合作研究：标记代数及其应用

• 批准号: 1600483
• 负责人: Florian Pfender
• 金额: $ 10万
• 依托单位: University of Colorado at Denver
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2019-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600483&HistoricalAwards=false
• 关键词: Collaborative; Research; Flag; Algebra; Its

Extremal graph theory studies properties of very large networks. Especially with the advent of interest in big data, such networks appear in a host of very important applications. In this project, the researchers focus on the density of small substructures appearing in large networks. The goal is to further develop a powerful method based on semidefinite programming, allowing its application to more complicated structures and longstanding problems in the field. The project involves undergraduate and graduate students. Open-source software under development in the project will be made readily available to other researchers. This research project aims to extend and develop the flag algebra method to new models in order to solve longstanding open problems, principally in extremal combinatorics. In prior work, the investigators and collaborators created a stability method and a blow-up technique using flag algebras. The stability method can be applied to solve problems, previously impervious to attack, where the extremal construction has an iterative structure. The blow-up technique translates questions on small graphs into the language of graph limits accessible to flag algebras, building bridges from one area of graph theory to another. This project will develop these techniques further for application to a number of important topics, including crossing numbers and small Ramsey numbers. It is expected that the work will draw on tools from linear and nonlinear programming to obtain exact results. The investigators will involve graduate students at their schools in the project and will work with graduate students from other schools during annual workshops.

极值图论研究非常大的网络的属性。特别是随着人们对大数据的兴趣的出现，此类网络出现在许多非常重要的应用中。在这个项目中，研究人员关注大型网络中出现的小型子结构的密度。目标是进一步开发一种基于半定规划的强大方法，使其能够应用于更复杂的结构和该领域长期存在的问题。 该项目涉及本科生和研究生。 该项目正在开发的开源软件将可供其他研究人员随时使用。该研究项目旨在将标志代数方法扩展到新模型，以解决长期存在的开放问题，特别是极值组合学中的问题。在之前的工作中，研究人员和合作者使用标志代数创建了稳定性方法和爆炸技术。稳定性方法可用于解决以前不受攻击影响的问题，其中极值构造具有迭代结构。爆炸技术将小图上的问题转化为标志代数可访问的图极限语言，建立了从图论的一个领域到另一个领域的桥梁。该项目将进一步开发这些技术，以应用于许多重要主题，包括交叉数和小拉姆齐数。预计这项工作将利用线性和非线性编程工具来获得准确的结果。调查人员将让其学校的研究生参与该项目，并将在年度研讨会上与其他学校的研究生合作。