Extremal and Structural Aspects of Graph Minor Theory

图小论的极值和结构方面

• 批准号: RGPIN-2017-05010
• 负责人: Norin, Sergey
• 金额: $ 1.46万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711397
• 关键词: Extremal; Structural; Aspects; Graph; Minor

The goal of this proposal is systematic investigation of extremal and structural properties of minor-closed classes of graphs. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations. One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term joint project with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain tight bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in large graphs. The PI also proposes investigation of extremal aspects of graph minor theory. One of the main goal of the proposal in this direction is to show that the density of every minor-closed class of graphs is attained by graphs of bounded pathwidth. The second goal is to compute density of particular minor-closed classes and develop generic tools for this type of problems. Finally, the PI proposes to investigate relaxations of Hadwiger's conjecture. Hadwiger's conjecture is a longstanding open problem, which greatly strengthens the four-color theorem. It is possibly the most famous open problem in graph theory. The PI has recently announced a proof, joint with Zdenek Dvorak, of one relaxation of the conjecture, improving on earlier results of Kawarabayshi and Mohar, Wood, and Liu and Oum. The PI proposes to extend this result in several directions, in particular, investigating intriguing connections with bootstrap percolation, a concept investigated in probabilistic combinatorics and theoretical physics.

该提案的目标是系统研究小闭类图的极值和结构特性。图次要理论是图论的一个深刻而丰富的领域，最初由 Robertson 和 Seymour 在一系列二十三篇论文中发展起来。它仍然是一个活跃的研究领域，具有广泛的算法应用。作为理论一部分开发的一些方法已成功应用于实际计算。 图次要理论的核心成果之一是 Robertson 和 Seymour 的图结构定理，它给出了不包含固定图作为次要的图的近似结构描述。 PI 建议继续与 Robin Thomas 进行长期联合项目，其目标是完善该理论的许多方面。特别是，该项目的目标之一是获得连通性的严格界限，以保证大图中某些次要项和相关配置（链接、拓扑次要项等）的存在。 PI 还建议对图次要理论的极值方面进行研究。该方向的提案的主要目标之一是表明每个次闭类图的密度是通过有界路径宽度的图获得的。第二个目标是计算特定次要封闭类的密度并为此类问题开发通用工具。 最后，PI 提议研究 Hadwiger 猜想的松弛。哈德维格猜想是一个长期存在的开放问题，它极大地加强了四色定理。这可能是图论中最著名的开放问题。 PI 最近与 Zdenek Dvorak 联合宣布了一项证明，证明了该猜想的一种松弛，改进了 Kawarabayshi 和 Mohar、Wood、Liu 和 Oum 的早期结果。 PI 提议将这一结果扩展到多个方向，特别是研究与自举渗透（概率组合学和理论物理学中研究的概念）之间有趣的联系。