Minors at large

未成年人在逃

• 批准号: EP/Y004302/1
• 负责人: Agelos Georgakopoulos
• 金额: $ 9.03万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY004302%2F1
• 关键词: Minors; large

The Robertson-Seymour Graph Minor theorem is one of the deepest and most important results in Graph Theory. It asserts that every family F of graphs that is closed under the minor relation can be determined by a finite list of "forbidden" substructures, in the sense that a graph G belongs to F if and only if G does not contain one of these substructures. This monumental theorem was proved in a series of twenty papers spanning over 500 pages, published from 1983 to 2004. The proof had many side-results that have had an independent impact on the area. An important implication of the Graph Minor theorem is that every family F as above can be recognised by an efficient algorithm. Moreover, many algorithmic problems that are known to be NP-hard in general are known to have efficient algorithms when restricted to such a family F.This project follows up on recent work by Fujiwara & Papasoglou and Bonamy et al. to develop a "Coarse Graph Minor Theory" that parallels the classical graph minor theory but introduces a coarse perspective following Gromov's paradigm of coarse geometry. Importantly, this new theorem applies not only to graphs, but to a much broader classes of metric spaces including Riemannian manifolds and many discrete metric spaces arising in computer science. We envisage a coarse version of a classical graph colouring problem that would have immediate algorithmic applications in problems of computational geometry. The importance of such problems is expected to grow due to the employment of geometric techniques in data science. We propose geometric analogues of other classical results of graph theory. In a second part, we attack a well known-conjecture of Thomas that seeks to extend the Robertson-Seymour Graph Minor Theorem to countably infinite graphs. We objerve that Thomas' conjecture would have an important implication for finite graphs as well, and propose a weaker version that would still have this implication and is much more likely to be accessible. We propose concrete steps for attacking the latter.

Robertson-Seymour图小定理是图论中最深刻、最重要的结论之一。它断言在次要关系下闭合的图族F可以由一个有限的“禁止”子结构列表确定，即当且仅当G不包含这些子结构之一时，图G属于F。这个不朽的定理在1983年到2004年间发表的20多篇论文中得到了证明，跨度超过500页。这一证明有许多副作用，对该领域产生了独立的影响。图小定理的一个重要含义是，上面的每一个族F都可以被一个有效的算法识别。此外，许多已知的NP-hard算法问题在被限制到这样一个族f时，已知具有有效的算法。本项目在Fujiwara & Papasoglou和Bonamy等人最近的工作的基础上，开发了一个“粗图小理论”，该理论与经典的图小理论平行，但引入了一个遵循Gromov粗几何范式的粗视角。重要的是，这个新定理不仅适用于图，还适用于更广泛的度量空间类别，包括黎曼流形和计算机科学中出现的许多离散度量空间。我们设想了一个经典图形着色问题的粗略版本，它将在计算几何问题中具有直接的算法应用。由于几何技术在数据科学中的应用，这些问题的重要性预计会增加。我们提出了图论其他经典结果的几何类似物。在第二部分中，我们攻击托马斯的一个著名猜想，该猜想试图将罗伯逊-西摩图小定理扩展到可数无限图。我们观察到托马斯的猜想对有限图也有重要的含义，并提出了一个更弱的版本，仍然有这个含义，更有可能是可访问的。我们提出了打击后者的具体步骤。