Collaborative Research: Flag Algebra Methods

合作研究：标记代数方法

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

Graph limits are a recent concept developed to study large graphs which can be used to simulate large networks. They bring together concepts from analysis and graph theory. Different languages were developed to provide statistics about the number of small subgraphs in large graphs. In particular, this project utilizes the machinery developed by Razborov called flag algebra. This machinery has been very effective in resolving many long standing open conjectures. The applications are usually computer assisted, which allows to construct proofs of a size impossible before. The project involves graduate and undergraduate students. The software developed during this project will be available to other researchers.The main topic of the research in this project is to extend the applications of flag algebra methods. These methods were developed by Razborov to attack a number of long standing open problems. In particular, the extension of Turan's Theorem to 3-uniform hypergraphs. In some cases, the application of the methods is quite straightforward. However, in applications with iterated extremal structure, the obtained result is usually not exact and additional work is needed. In prior work, the investigators and their collaborators developed methods for dealing with iterated constructions. An example of this problem is the question to maximize the number of induced 5-cycles in a graph. In this project the investigators will further develop these methods. Iterated structures appear in many contexts, for example in the polynomial to exponential transition in Ramsey theory. Another direction of the project is to extend the method to small graphs. In prior work, the investigators have applied such ideas to Ramsey numbers and to Erdos' Pentagon problem. The investigators will refine these methods and apply them in other contexts. Graduate students will be included in the research projects and the investigators will continue to support the annual graduate research workshop in combinatorics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图形限制是一个最近开发的概念，用于研究大图，可用于模拟大型网络。他们将分析和图理论的概念汇总在一起。开发了不同的语言，以提供有关大图中的小型子图数量的统计信息。特别是，该项目利用Razborov开发的名为Flag代数的机械。这种机械在解决许多长期的开放猜想方面非常有效。应用程序通常是计算机辅助的，这可以构建以前不可能的大小的证据。该项目涉及毕业生和本科生。该项目期间开发的软件将用于其他研究人员。该项目的研究主要主题是扩展FLAG代数方法的应用。这些方法是由Razborov开发的，以攻击许多长期存在的开放问题。特别是将Turan定理扩展到3-均匀的超图。在某些情况下，这些方法的应用非常简单。但是，在具有迭代极端结构的应用中，获得的结果通常不准确，需要额外的工作。在先前的工作中，调查人员及其合作者开发了处理迭代结构的方法。这个问题的一个例子是一个问题，是在图中最大化诱导的5个周期的数量。在这个项目中，调查人员将进一步开发这些方法。迭代结构出现在许多情况下，例如在拉姆齐理论中的多项式向指数过渡中。该项目的另一个方向是将方法扩展到小图。在先前的工作中，调查人员已将此类想法应用于拉姆齐数字和Erdos的五角大楼问题。调查人员将完善这些方法并将其应用于其他情况。研究生将被纳入研究项目，研究人员将继续支持Combinatorics的年度研究生研究研讨会。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，认为值得通过评估值得支持。

项目成果

Semidefinite Programming and Ramsey Numbers

• DOI: 10.1137/18m1169473
• 发表时间: 2017-04
• 期刊: SIAM J. Discret. Math.
• 作者: Bernard Lidick'y;Florian Pfender

Inducibility of directed paths

有向路径的可归纳性

• DOI: 10.1016/j.disc.2020.112015
• 发表时间: 2020
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Choi, Ilkyoo;Lidický, Bernard;Pfender, Florian
• 通讯作者: Pfender, Florian

Counterexamples to a Conjecture of Harris on Hall Ratio

哈里斯霍尔比猜想的反例

• DOI: 10.1137/18m1229420
• 发表时间: 2022
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Blumenthal, Adam;Lidický, Bernard;Martin, Ryan R.;Norin, Sergey;Pfender, Florian;Volec, Jan
• 通讯作者: Volec, Jan

Edge‐maximal graphs on orientable and some nonorientable surfaces

• DOI: 10.1002/jgt.22705
• 发表时间: 2019-11
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: James Davies;Florian Pfender

Sharp bounds for decomposing graphs into edges and triangles

将图分解为边和三角形的锐界

• DOI: 10.1017/s0963548320000358
• 发表时间: 2021
• 期刊: Probability and Computing
• 作者: Blumenthal, Adam;Lidický, Bernard;Pehova, Yanitsa;Pfender, Florian;Pikhurko, Oleg;Volec, Jan
• 通讯作者: Volec, Jan