Collaborative Research: Flag Algebra and Its Applications

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

基本信息

批准号：
1600390
负责人：
Bernard Lidicky
金额：
$ 8万
依托单位：
Iowa State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-07-01 至 2019-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600390&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.

极端图理论研究了非常大的网络的特性。尤其是随着大数据感兴趣的出现，此类网络出现在许多非常重要的应用程序中。在这个项目中，研究人员专注于大型网络中出现的小型子结构的密度。目的是进一步开发一种基于半决赛编程的强大方法，从而使其应用于该领域更复杂的结构和长期存在的问题。该项目涉及本科生和研究生。该项目正在开发的开源软件将容易为其他研究人员提供。该研究项目旨在将国旗代数方法扩展和开发到新模型，以解决长期存在的开放问题，主要是在极端组合中。在先前的工作中，调查人员和合作者使用FLAG代数创建了一种稳定方法和爆破技术。稳定方法可以应用于解决以前不受攻击的问题，在极端结构具有迭代结构的情况下。爆破技术将小图上的问题转化为图形限制的语言，可以通过标志代数访问，从图理论的一个区域建造桥梁到另一个区域。该项目将进一步开发这些技术，以应用于许多重要主题，包括交叉数字和小的拉姆西数字。预计该工作将利用线性和非线性编程的工具来获得确切的结果。调查人员将使他们的学校参与研究生，并将在年度研讨会期间与其他学校的研究生合作。