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 algebra的机器。这一机制在解决许多长期悬而未决的问题方面非常有效。这些应用程序通常是计算机辅助的，这允许构建以前不可能的大小的证明。该项目涉及研究生和本科生。本计画所开发之软体将提供给其他研究者使用，本计画之主要研究内容为扩展旗标代数方法之应用。这些方法是由Razborov开发的，用于攻击一些长期存在的开放问题。特别地，将Turan定理推广到3-一致超图。在某些情况下，这些方法的应用非常简单。然而，在具有迭代极值结构的应用中，所得到的结果通常是不准确的，并且需要额外的工作。在之前的工作中，研究人员和他们的合作者开发了处理迭代结构的方法。这个问题的一个例子是最大化图中诱导的5-圈数的问题。在这个项目中，研究人员将进一步发展这些方法。迭代结构出现在许多情况下，例如在拉姆齐理论中的多项式到指数转换中。该项目的另一个方向是将该方法扩展到小图。在之前的工作中，研究人员已经将这些想法应用于拉姆齐数和鄂尔多斯的五角大楼问题。研究人员将改进这些方法，并将其应用于其他情况。研究生将被纳入研究项目，研究人员将继续支持组合学的年度研究生研究研讨会。该奖项反映了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