Graph Minor Theory in three dimensions and Connectivity

点击翻译按钮获取中文摘要

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.