Dr. Jan Kurkofka

I am a research fellow of Johannes Carmesin at University of Birmingham.

E-Mail: j.lastname (at) bham.ac.uk

Teaching in Winter 2022

Graph Minors

Teaching in previous semesters

Selected talks

IBS DIMAG Virtual Discrete Math Colloquium, May 2022.
Cambridge Combinatorics Seminar, November 2021.
Warwick Combinatorics Seminar, February 2021.

Meet me at upcoming conferences

CanaDAM, June 2023.

Research interests

My research interests include graph minors, connectivity, graph-decompositions, graph coverings and 3D combinatorics. I have also studied the combinatorial and topological aspects of infinite graphs, with the overarching aim of better understanding the structure of infinite graphs. Specifically, this includes:

Local-global graph theory

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.

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 result raises many more questions that I investigate in this project.

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 integer $k\ge 1$, the whirl graph contains $k$ edge-disjoint order-compatible $u$-$v$ paths but not infinitely many.

End spaces

The ends of a graph can be thought of as points at infinity towards which its one-way infinite paths converge. Adding the ends to a graph extends its structure naturally, and the arising extension is the foundation of modern infinite graph theory. If the graph is locally finite in that all its vertices have only finitely many neighbours, then the extension is a well-known and thoroughly studied compactification with various applications. But if the graph is not locally finite, then the extension is not a compactification, and there are still many open questions. For instance, which graphs admit end-faithful spanning trees, spanning trees whose one-way infinite paths roughly correspond to the ends of the graph?

Star-comb series

The star-comb lemma is a standard tool in infinite graph theory which tells us something about the nature of connectedness in infinite graphs: that the way in which they link up their infinite sets of vertices can take two fundamentally different forms, a star or a comb. Stars and combs, however, do not exclude each other, and so it is natural to ask for structures whose existence is dual, in the sense of complementary, to the existence of a star or a comb at a given vertex set. Bürger and I determined complementary structures for stars, combs, and all relevant combinations thereof, in a series of four papers. The techniques that we used in our proofs span the whole breadth of non-set-theoretic infinite graph theory and include tools from general topology. As a consequence, the series establishes a new unified perspective on the whole arsenal of combinatorial and topological tools in infinite graph theory.

Publications and preprints

Local-global graph theory

(with R. Diestel, Raphael W. Jacobs and P. Knappe) Graph Decompositions via Coverings, 2022, submitted. (arXiv)

Tangles

(with Johannes Carmesin) Entanglements, 2022. (arXiv)

Farey graph

Every infinitely edge-connected graph contains the Farey graph or $T_{\aleph_0}\!\ast t$ as a minor, Mathematische Annalen 382 (2022), 1881-1900. ( Journal | arXiv )

(with Paul Knappe) The immersion-minimal infinitely edge-connected graph, 2022, submitted. (arXiv)

The Farey graph is uniquely determined by its connectivity, Journal of Combinatorial Theory, Series B 151 (2021), 223-234. ( Journal | arXiv )

Ubiquity and the Farey graph, European Journal of Combinatorics 95 (2021), 103326. ( Journal | arXiv )

End spaces

(with Max Pitz) A representation theorem for end spaces of infinite graphs, 2021, submitted. (arXiv)

(with Stefan Geschke, Ruben Melcher and Max Pitz) Halin's end degree conjecture, Israel Journal of Mathematics (2022). ( Journal | arXiv )

(with Ruben Melcher and Max Pitz) Approximating infinite graphs by normal trees, Journal of Combinatorial Theory, Series B 148 (2021), 173-183. ( Journal | arXiv )

(with Ruben Melcher) Countably determined ends and graphs, Journal of Combinatorial Theory, Series B 156 (2022), 31-56. ( Journal | arXiv )

(with Carl Bürger) End-faithful spanning trees in graphs without normal spanning trees, Journal of Graph Theory (2022). ( Journal | arXiv )

(with Ruben Melcher and Max Pitz) A strengthening of Halin's grid theorem, Mathematika 68(4) (2022). ( Journal | arXiv )

Star-comb series

(with Carl Bürger) Duality theorems for stars and combs I: Arbitrary stars and combs, Journal of Graph Theory 99(4) (2022), 525-554. ( Journal | arXiv )

(with Carl Bürger) Duality theorems for stars and combs II: Dominating stars and dominated combs, Journal of Graph Theory 99(4) (2022), 555-572. ( Journal | arXiv )

(with Carl Bürger) Duality theorems for stars and combs III: Undominated combs, Journal of Graph Theory 100(1) (2022), 127-139. ( Journal | arXiv)

(with Carl Bürger) Duality theorems for stars and combs IV: Undominating stars, Journal of Graph Theory 100(1) (2022), 140-162. ( Journal | arXiv)

Ends and tangles

(with Max Pitz) Tangles and the Stone-Čech compactification of infinite graphs, Journal of Combinatorial Theory, Series B 146 (2021), 34-60. ( Journal | arXiv )

(with Max Pitz) Ends, tangles and critical vertex sets, Mathematische Nachrichten 292(9) (2019), 2072-2091. ( Journal | arXiv )

(with Ann-Kathrin Elm) A tree-of-tangles theorem for infinite tangles, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (2022). ( Journal | arXiv )

Connectivity

(with Raphael W. Jacobs, Attila Joó, Paul Knappe and Ruben Melcher) The Lovász-Cherkassky theorem for locally finite graphs with ends, 2021, submitted. (arXiv)

(with Christian Elbracht and Maximilian Teegen) Edge-connectivity and tree-structure in finite and infinite graphs, 2021. (arXiv)

Theses

Dissertation (2020, Summa Cum Laude): Ends and tangles, stars and combs, minors and the Farey graph. (PDF)

Master's thesis (2017, 1.0): On the tangle compactification of infinite graphs. (arXiv)

	Local-global graph theory 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.

	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 result raises many more questions that I investigate in this project.

	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 integer $k\ge 1$, the whirl graph contains $k$ edge-disjoint order-compatible $u$-$v$ paths but not infinitely many.

	End spaces The ends of a graph can be thought of as points at infinity towards which its one-way infinite paths converge. Adding the ends to a graph extends its structure naturally, and the arising extension is the foundation of modern infinite graph theory. If the graph is locally finite in that all its vertices have only finitely many neighbours, then the extension is a well-known and thoroughly studied compactification with various applications. But if the graph is not locally finite, then the extension is not a compactification, and there are still many open questions. For instance, which graphs admit end-faithful spanning trees, spanning trees whose one-way infinite paths roughly correspond to the ends of the graph?

	Star-comb series The star-comb lemma is a standard tool in infinite graph theory which tells us something about the nature of connectedness in infinite graphs: that the way in which they link up their infinite sets of vertices can take two fundamentally different forms, a star or a comb. Stars and combs, however, do not exclude each other, and so it is natural to ask for structures whose existence is dual, in the sense of complementary, to the existence of a star or a comb at a given vertex set. Bürger and I determined complementary structures for stars, combs, and all relevant combinations thereof, in a series of four papers. The techniques that we used in our proofs span the whole breadth of non-set-theoretic infinite graph theory and include tools from general topology. As a consequence, the series establishes a new unified perspective on the whole arsenal of combinatorial and topological tools in infinite graph theory.