Collaborative Research: Flag Algebra and Its Applications

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

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.