Graph Minors in 3D and Connectivity

• Applicant: Professor Dr. Johannes Carmesin
• Subject Area: Mathematics
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 546892829

Graph Minor Theory sits at the interface between Topology and Graph Theory, with many algorithmic applications. The area started with Kuratowski's characterization of planarity in terms of forbidden minors as well as the famous Hadwiger Conjecture, which would be a far reaching generalization of the famous Four-Color-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 characterizes 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, 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. There is potential for applications in connection to computer aided design. My main aim in this program 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 program I intend to extend this further. A second strand of this program is the development of new methods for extremal questions in graph minors and connectivity. On the one hand connectivity questions arise in applications, on the other hand they provide fundamental tools for the theory. This program contains a new approach towards a fundamental problem in this area from the 70s.

• DFG Programme: Research Grants