Graph Minor Theory in three dimensions and Connectivity

图子论位于拓扑学和图论的交界处，有许多算法应用。这一领域始于库拉托夫斯基对禁止未成年人的平面性的描述，以及著名的哈德威格猜想，这将是著名的四色定理的深远推广。图的子集理论的一个重要方面是图在二维曲面上的嵌入与子集之间的联系。这里，通过删除边并将连通边集压缩到单个顶点来获得图的一小部分。在平面图的上下文中，次关系是特别自然的；它等价于子图关系与平面对偶相结合。这种联系的发现始于20世纪30年代的库拉托夫斯基定理，并导致了罗伯逊-西摩定理的证明，该定理通常被认为是当今组合学中最深刻的定理。罗伯逊和西摩的图形次要理论对整个组合学产生了革命性的影响，并对计算机科学产生了深刻的影响。简而言之，它们的结构定理建立了图上的次要关系和图在2维曲面上的嵌入之间的联系。这种联系的最简单的例子是1930年库拉托夫斯基的平面性准则，它用禁止的未成年人来刻画平面图的类。最近，我能够证明库拉托夫斯基定理的一个三维类比，回答了洛瓦兹、帕尔顿和瓦格纳的问题。这表明，图形未成年人的思想和方法可以从2个维度扩展到3个维度。他们是否为解决三维流形上的著名问题提供了新的方法？这样的问题在纯数学和工程应用中都会出现：事实上，佩雷尔曼证明了任何单连通的紧致3-流形都同构于3-球面，解决了7千年问题之一。证明我的新3D-Kuratowski定理的要素之一是Perelman定理，因此我的结果提供了组合学、几何学和拓扑学之间的联系。工程应用源于这样一个事实，即现实世界中的许多结构可以由所谓的2-复合体来建模；也就是说，物体可以通过在其边界处将三角形面粘在一起而获得。例子包括摩天大楼或汽车等人类建造的结构，泡沫和肠道等物理结构具有医疗应用。这种2-复合体何时能嵌入到真实的三维世界中是一个基本问题。更具体地说，给出一个抽象的2-复合体，你能在3-空间中使用弯曲、拉伸和扭曲来组装它的面，从而使这些面不会相互刺穿吗？这个项目将对这类问题有更好的组合理解，从而为相应的计算问题带来更好的算法。我在这个项目中的主要目标是开发一个关于2-复形的图子理论。我相信这有可能成为一个丰富的新理论，有许多令人兴奋的问题，并与组合学(特别是图的子式和连通性)、代数(更具体地说是拟阵理论)、微分几何和三维流形的拓扑学和算法有联系。最近在这一领域取得的成功包括我的二次时间算法来检查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.