Collaborative Research: Flag Algebra and Its Applications

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

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.