Graph Minor Theory in three dimensions and Connectivity

图小理论位于拓扑学和图论之间的接口，具有许多算法应用。这一领域始于库拉托夫斯基对平面性的描述，即禁止小调，以及著名的哈德维格猜想，这将是著名的四色定理的深远推广。图次元论的一个重要方面是二维曲面上图的嵌入与次元关系之间的联系。这里通过删除边并将连通边集压缩为单个顶点来获得图的次边。在平面图中，小关系是特别自然的；它等价于结合了平面对偶的子图关系。这种联系的发现始于20世纪30年代的库拉托夫斯基定理，并导致了罗伯逊-西摩定理的证明，该定理通常被认为是当今组合学中最深奥的定理。Robertson和Seymour的图次理论对组合学产生了变革性的影响，对计算机科学有着深远的影响。粗略地说，他们的结构定理建立了图上的次要关系和二维曲面上图的嵌入之间的联系。这种联系的最简单的例子是1930年Kuratowski的平面性准则，它用禁忌次元来描述平面图的类别。最近，我已经证明了库拉托夫斯基定理的三维模拟，回答了洛瓦兹、帕顿和瓦格纳的问题。这表明图次元的思想和方法可以从二维扩展到三维。它们是否提供了解决众所周知的3-流形问题的新方法？这样的问题在纯数学和工程应用中都有出现：事实上，佩雷尔曼证明了任何单连通紧致3流形与3球同构，解决了7千年问题之一。我的新3D-Kuratowski定理的证明要素之一是Perelman定理，因此我的结果提供了组合学，几何学和拓扑学之间的联系。工程应用源于这样一个事实：现实世界中的许多结构都可以用所谓的2-复合物来建模；也就是说，可以通过在其边界粘合三角形面来获得的对象。例子包括人造结构，如摩天大楼或汽车，物理结构，如泡沫和肠道，用于医疗应用。这是一个基本的问题，当这样的2-复合物可以嵌入到实际的三维世界。更具体地说，以抽象的方式给出一个2复合体，你能在3空间中使用弯曲、拉伸和扭曲来组合它的面，使其面不会相互刺穿吗？这个项目将产生对这些问题的更好的组合理解，这反过来将导致更好的算法来解决相应的计算问题。我在这个项目中的主要目的是为2-复合体发展一个图小理论。我相信这有可能成为一个丰富的新理论，有许多令人兴奋的问题，并与组合学（特别是图的次要部分和连通性），代数（更具体地说是矩阵理论），微分几何和3流形拓扑和算法的联系。最近在这个领域的成功包括我的二次时间算法来检查3空间中单连通2-复合体的可嵌入性，在这个项目中，我打算进一步扩展这一点。该计划的第二部分是开发图小段和连通性极值问题的新方法。一方面，连接问题出现在应用中（如互联网或电力网络的可靠性问题），另一方面，它们为理论提供了基本工具（如Tutte的分解定理或Robertson和Seymour的缠结树定理）。该方案包含了解决70年代以来这一领域一个根本问题的新方法。

Graph Minor Theory sits at the interface between Topology and Graph Theory, with many algorithmic applications. The area started with Kuratowski's characterisation of planarity in terms of forbidden minors as well as the famous Hadwiger Conjecture, which would be a far reaching generalisation of the famous Four-Colour-Theorem. An important aspect of Graph Minor Theory is the connection between embeddings of graphs in 2-dimensional surfaces and the Minor Relation. Here a minor of a graph is obtained by deleting edges and contracting connected edge sets to single vertices. In the context of plane graphs the minor relation is particularly natural; it is equivalent to the subgraph relation combined with planar duality. The discovery of this connection began with Kuratowski's theorem in the 1930s and led to the proof of the Robertson-Seymour Theorem, which is often regarded as the deepest theorem of Combinatorics today. The Graph Minor Theory of Robertson and Seymour has had a transformative impact on Combinatorics as a whole with deep implications to Computer Science. In very rough terms, their structure theorem establishes a connection between the minor relation on graphs and embeddings of graphs in 2-dimensional surfaces. The simplest example of this connection is Kuratowski's planarity criterion from 1930, which characterises the class of planar graphs in terms of forbidden minors. Recently, I have been able to prove a 3-dimensional analogue of Kuratowski's theorem, answering questions of Lovasz, Pardon and Wagner. This suggests that the ideas and methods of Graph Minors can be extended from 2 to 3 dimensions. Do they offer new approaches to well-known problems on 3-manifolds? Such problems occur both in Pure Mathematics and Engineering Applications: indeed, Perelman proved that any simply connected compact 3-manifold is isomorphic to the 3-sphere, solving one of the 7 millennium problems. One of the ingredients of the proof of my new 3D-Kuratowski theorem is Perelman's theorem, and thus my result provides a link between Combinatorics, Geometry and Topology. Engineering applications arise from the fact that many structures in the real world can be modelled by so called 2-complexes; that is, objects that can be obtained by gluing together triangular faces at their boundaries. Examples include human-built structures like skyscrapers or cars, physical ones like foams and intestines give medical applications. It is a fundamental question when such 2-complexes can be embedded in the real 3-dimensional world. More specifically, given a 2-complex in an abstract way, can you assemble its faces - using bending, stretching and twisting - in 3-space so that the faces do not pierce each other? This project will yield a better combinatorial understanding of such problems, which in turn will lead to better algorithms for the corresponding computational problems.My main aim in this programme is to develop a Graph Minor Theory for 2-complexes. I believe that this has the potential to become a rich new theory, with many exciting questions, and connections to Combinatorics (in particular Graph Minors and connectivity), Algebra (more specifically Matroid Theory), Differential Geometry and Topology of 3-manifolds and Algorithms. Recent successes in this area include my quadratic time algorithm to check embeddability of simply connected 2-complexes in 3-space - and during this programme I intend to extend this further. A second strand of this programme is the development of new methods for extremal questions in graph minors and connectivity. On the one hand connectivity questions arise in applications (such as reliability questions for the internet or electrical power networks), on the other hand they provide fundamental tools for the theory (such as Tutte's Decomposition Theorem or the Tangle-Tree Theorem of Robertson and Seymour). This programme contains a new approach towards a fundamental problem in this area from the 70s.