New Approaches to Decomposition in Graph-Minor Theory

• Applicant: Dr. Jan Kurkofka
• Subject Area: Mathematics
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 566118291

The Graph Minor Theorem, proved over a period of 20 years on 500 pages by Robertson and Seymour, is one of the deepest theorems in Mathematics. A graph X is a minor of a graph G if X can be obtained from G by successively deleting vertices or edges and by contracting edges to vertices. The Theory of Graph Minors is concerned with the study of graph-classes that are closed under taking minors. For example, the graphs that are planar, in that they can be drawn in the plane without crossings, form such a class. A foundational result in the area is Kuratowski's Theorem, which states that a graph is planar if and only if it contains neither the graph on five vertices with all possible edges, nor the graph on 3 vs 3 vertices with all possible cross-edges, as a minor. The Graph Minor Theorem is a far-reaching extension of Kuratowski's Theorem: it states that for every minor-closed class of graphs there exists a list of just finitely many excluded minors that characterises the class. Examples of minor-closed classes range from topological classes, such as graphs that embed in a fixed surface or graphs that knotlessly embed in 3-space, to graphs that look like trees (have bounded tree-width) which play an important role in Complexity Theory. A groundbreaking implication of the Graph Minor Theorem to Computer Science is that for each minor-closed graph-class there exists a cubic-time algorithm that decides membership in it. Graph Minor Theory has deep implications both within Mathematics and to Computer Science. My aim is to push forward the boundaries of Graph Minor Theory, by proving new structure theorems that open the gates for applications to major challenges in Computer Science, Data Science and Algebra: 1. Develop new versatile tools to compute the excluded minors for minor-closed graph-classes. While Courcelle et al. proved that there is no algorithm that, given a sentence (in monadic second-order logic) describing a minor-closed graph-class, computes an excluded minors characterisation of the class, the problem of determining the excluded minors for particular classes - and by doing so providing a cubic time membership test - is of utmost importance in Computer Science. 2. Data Science sets new challenges for Mathematics. A central challenge is to study the structure of large sparse networks, coming from applications such as infrastructure networks, social networks or biological networks. The full potential of Graph Minor Theory in this area has yet to be harnessed. 3. In Algebra, a longstanding quest is to expand Bass-Serre Theory to finite groups. Groups are a core concept in Mathematics that describe the symmetries of objects. By considering geometric representations of groups such as their Cayley graphs, it becomes possible to study groups using tools from Combinatorics. Pushing the boundaries of Graph Minor Theory towards more explicitness and the inclusion of sparse networks opens the gates for applications to groups.

• DFG Programme: Research Grants