权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

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