Dr. Jan Kurkofka

News

  • Talk at Kolkom on Canonical graph decompositions and local separators: From coverings to a combinatorial theory
firstname.lastname the-sign math.tu-freiberg.de

TU Bergakademie Freiberg


Selected Publications


Teaching

  • Algorithmic Geometry
  • Reading Group Discrete Structures (Topic: Bass-Serre Theory)
Teaching in previous semesters

Selected talks


Research interests

My research interests include Graph Minor Theory, Connectivity Theory, Topological Graph Theory, Infinite Graph Theory, and intradisciplinary applications thereof. Here are some ongoing and recent projects:

Explicit structure theorems for low connectivity

Decomposing graphs into highly connected regions is a foundational method in Graph Minor Theory, and Connectivity Theory more broadly. Explicit solutions to the following problem for any k would be tremendously useful for computing excluded minors: Decompose every k-connected graph along k-separators into smaller pieces that are (k + 1)-connected or 'basic'. The first step k = 1 is given by the block-cutvertex decomposition. For k = 2, the solution is a classical theorem of Tutte from 1966, which builds on earlier works of Whitney from the 1930s. It was long believed that Tutte's Theorem cannot be fully extended to higher connectivity. I recently proposed a new perspective on graph connectivity that allowed me to prove a Tutte-Theorem for k = 3 with Carmesin. Can this be extended to larger k ?

 
Local-global invariants of graphs and groups

The question to what extent graph invariants - the chromatic number, say, or connectivity - are of local or global character, and how their local and global aspects interact, drives much of the research in graph theory both structural and extremal. This project offers such studies a possible formal basis. In our main paper we combine coverings, as known from Topology, with tangle-tree decompositions as known from Graph Minor Theory, to canonically decompose finite graphs and groups into their highly connected local parts. The global structure of the graph or group, as determined by the relative position of these parts, is then described by a coarser model. I am currently working on applications of our result and methodoloy in Computer Science and Combinatorial Group Theory.

 
Farey graph

The Farey graph, shown on the left and surveyed on 300 pages in Hatcher's new book (PDF), plays a role in a number of mathematical fields ranging from group theory and number theory to geometry and dynamics. Curiously, graph theory has not been among these until very recently, when I showed that the Farey graph plays a central role in graph theory too: it is one of two infinitely edge-connected graphs that must occur as a minor in every infinitely edge-connected graph. Previously it was not known that there was any set of graphs determining infinite edge-connectivity by forming a minor-minimal list in this way, let alone a finite set. This resulted marked the starting point of a project in which I addressed exciting follow-up questions.

 
The whirl graph on the left answers three questions about the Farey graph at once. For instance, the whirl graph is infinitely edge-connected and contains the Farey graph as a minor with branch sets of size two, but it does not contain a subdivision of the Farey graph. In fact, the whirl graph contains no subdivision of any naively constructed infinitely edge-connected graph, because it has the following property: For any two vertices u,v and any positive integer k, the whirl graph contains k edge-disjoint order-compatible u–v paths but not infinitely many.


Publications and preprints

Explicit structure theorems for low connectivity

Local-global invariants of graphs and groups

Combinatorics in 3D

Farey graph

End spaces

Star-comb series

Ends and tangles

General connectivity


Theses