
Forschungsschwerpunkt
Diskrete Mathematik
Aktuelle
Forschungsprojekte – Current Research Projects (former
projects)
Graph
Theory
For guidance on graph theory in general
see R. Diestel, Graph
Theory, Springer GTM173. Our current research
projects are as follows:
Project

Summary

Details

Contact

Tangles‑and trees

Tangles, originally
introduced for graphs by Robertson and Seymour in
1988, set a new paradigm for local high
connectivity in discrete structures: rather than
being specified by conditions on the substructure
itself, such as the existence of edges or paths
linking up the vertices of a subgraph, tangles
capture high local connectivity by orienting all
loworder separations towards it.
We study two types of
tangle theorems. Treeoftangles theorems find a
nested  and hence small  set of
separations that suffice to distinguish all
tangles that can be distinguished at all. These
separations cut up the entire structure in a
treelike way, the tree of tangles, so that the
highly connected substructures described by the
tangles are found in nodes, or small subtrees, of
this tree. Tangletree duality theorems
provide a more radical tree structure for discrete
structures that have no tangle of a given order at
all: here, the nodes are too small to accommodate
such a tangle, and so the tree structure witnesses
their nonexistence in a tangible way.
Our aims in this area are
twofold. We seek theorems of the above type under
weaker and weaker conditions, so that such
abstract theorems may become applicable in wider
contexts. So far, applications include a
new  tanglelike  treewidth duality
theorem for finite graphs, a canonical tangletree
theorem for finite matroids, and a combination of
both types of theorem in which those parts of a
tangledistinguishing treedecomposition that are
not home to a tangle are further refined by a
treedecomposition that witnesses the absence of a
tangle in that part.

Basic
tangletree duality paper
Basic
treeoftangles paper
All
papers

Nathan
Bowler
Johannes Carmesin
Reinhard
Diestel Joshua
Erde
Pascal
Gollin
Matthias
Hamann
Daniel Weißauer

Abstract separation systems,
with applications to clustering and image
segmentation

The properties of
tangles and the separations distinguishing them
that are needed for the tangletree theory
outlined above can be stated in terms of these
separations alone, without reference to anything
that they `separate'. This has enabled us to
reprove those theorems in an axiomatic setting of
such abstract separation systems:
partially ordered sets with a handful of
properties laid down as axioms.
Abstract separation systems, and
tangles in these, offer a radically new
approach to cluster analysis in big data sets.
As an example, we have outlined a tanglebased
approach to image segmentation (Mona Lisa
paper), and have are in touch with the IT
industry about implementations of this approach.
The abstract theory can also be
reapplied to separations of infinite graphs.
Since these have finitary descriptions, they can
be viewed as inverse limits of finite graph
separations, to which the theory applies. Our aim,
then, is to develop a tangletree duality theory
for infinite graphs and matroids from this theory
of profinite abstract separation systems.

Basic
paper
Mona
Lisa paper
All
papers
Patent

Nathan
Bowler
Reinhard
Diestel
Christian
Elbracht
Joshua
Erde
Pascal
Gollin
Jakob Kneip
Max
Teegen

Infinite matroids

The development of
a workable theory of infinite matroids only became
practicable in 2010 with the discovery by Bruhn,
Diestel, Kriesell, Pendavingh and Wollan of
cryptomorphic axiomatisations for infinitary
matroids parallel to those for finite matroids.
Since then the field has grown rapidly, with
particular progress being made in understanding
connectivity, tree decompositions,
representability, matroid union, base packing and
covering, and the links to topological infinite
graph theory via representations of matroids over
graphlike topological spaces. Infinite gammoids
and infinite oriented matroids have also been
intensively investigated.
The current shortterm
aim within this project is to develop a structural
theory of infinite matroids, beginning with an
analogue of Seymour’s decomposition theorem for
regular matroids. There are also ongoing
investigations of weak notions of representability
and of the structure of the lattice of cyclic
flats of infinite matroids. Central problems with
broad implications, but requiring an intensive
longerterm research effort, include the Farkas
Lemma for infinite regular matroids and the
infinite matroid intersection conjecture. A
further longterm subproject is the development of
further applications within topological infinite
graph theory and infinitary analogues of linear
algebra.

Basic
paper
All
papers

Hadi Afzali
Nathan
Bowler
Johannes
Carmesin
Reinhard
Diestel
AnnKathrin Elm
Stefan
Geschke
Hendrik Heine
HiuFai Law

Tangle‑compactifications
of infinite graphs

Locally finite
graphs can be compactified by adding their ends.
Over the last 15 years it has been shown  in
an effort carried largely by mathematicians in our
group  that this topological setting
provides what appears to be the 'right' framework
for studying locally finite graphs. Indeed, many
classical theorems from finite graph theory that
involve paths or cycles have been shown to
generalize to locally finite infinite graphs in
this topological setting, while failing to
generalize in a purely combinatorial infinite
setting.
This project aims to carry
these past successes further to arbitrary infinite
graphs. For these, adding their ends does not
suffice to provide a suitable compactification.
But we have been able to show that adding their
tangles of infinite order does. Such tangles come
in two types: tangles induced by ends, and others,
which correspond to points in the inverse limit of
nonprincipal ultrafilters on the graph's
components obtained by deleting finite sets of
vertices. 
Basic
paper
All
papers

Reinhard
Diestel
Jan Kurkofka
Max
Pitz

Extremal infinite
graph theory

The notion of
topological paths and circles in G has made
it possible to extend theorems about paths and
cycles in finite graphs to locally finite graphs,
even in cases where their verbatim generalizations
fail. Combined with the new notion of end degrees,
it is also possible now to consider density
problems typical for sparse extremal graph theory,
such as which substructures are forced by certain
minimumdegree assumptions. Results so far include
sufficient conditions for forcing subgraphs of
given connectivity; for the existence of disjoint
paths joining two given sets of vertices or ends;
for the existence of edgedisjoint spanning trees;
or for the existence of a Hamilton circle,
a topological circle in G that passes through every
vertex and every end. In particular, we have
topological versions of Menger's theorem, of the
Tutte/NashWilliams tree packing theorem, and of
Fleischner's theorem that the square of a
2connected finite graph contains a Hamilton
cycle.
Open problems currently
studied include the existence of a Hamilton circle
in 4connected line graphs, extending a theorem of
Asratian and Khachatrian about Hamilton cycles in
finite graphs to locally finite ones, and how to
force certain infinite minors or subdivisions by
assuming high connectivity. 
Basic
paper
All
papers

Reinhard
Diestel
Matthias
Hamann
Pascal
Gollin
Karl Heuer
Max
Pitz

Ubiquity in
infinite graphs

A classical result
of Halin states that if a graph G contains n disjoint
rays for every positive integer n then G contains
infinitely many disjoint rays. The question how
this generalizes to other graphs than rays leads
to the notion of ubiquity with respect to a
relation between graphs. Typical relations to be
considered in this context are the subgraph
relation, the topological minor relation,
NashWilliams's immersion relations, and the minor
relation. Surprisingly, ubiquity problems turned
out to be closely related to questions of
wellquasiordering. The project aims at
establishing ubiquity results, especially for
locally finite graphs and with respect to the
minor relation.

Papers

Nathan
Bowler
Johannes
Carmesin
Christian
Elbracht
Joshua
Erde
Pascal
Gollin
Karl Heuer
Max
Pitz
Max
Teegen

Geometric aspects
of tree‑width

A treedecomposition
of a graph can be regarded as an approximation of
its global structure by a tree. The quality of
this approximation is usually measured by the width, the
maximum size of a part of the decomposition,
aiming at a correspondence between the tree and
the arrangement of highly connected substructures
within the graph. This concept is, however, not
apt to capture two of its central inherent
features: distance and closeness. To overcome this
shortcoming, we have initiated the study of
treedecompositions where every part induces a
connected subgraph, so that large distances are
necessarily reflected by size, yielding a notion
of connected
treewidth. We identified and isolated
the key obstructions for this parameter and showed
how it relates to other graph invariants, such as
hyperbolicity. The quest for a duality theorem has
led us to a relaxation of the original notion, but
the question of how much these two actually differ
is still open and appears to be a natural question
about the rigidity of treedecompositions. An
unforeseen byproduct of our studies has been a
metric viewpoint of treewidth itself, the
clarification of which is the subject of further
research.

Papers 
Reinhard
Diestel
Matthias
Hamann
Daniel Weißauer

Infinite directed
graphs

In this most
recent of our projects we study how theorems about
finite directed graphs extend to infinite directed
graphs. We use the techniques developed here for
infinite undirected graphs and try to apply them
in the different setting of directed graphs.
One main focus in this
project is to generalize an important minmax
theorem by Lucchesi and Younger to infinite
digraphs: is it possible to find a set of disjoint
finite directed cuts (dicuts) together with a set
of edges covering all finite dicuts such that
every dicut of the disjoint set contains precisely
one of these edges? We already proved some
interesting special cases, but the general
conjecture remains open.
Another branch of this
project deals with generalising Edmonds' branching
theorem. While a straightforward generalisation
fails as the treepacking theorem for undirected
graphs, we could generalise the theorem with a
notion inspired by topological spanning trees of
undirected graphs.
Future questions of this
project are about whether the existence of
unboundedly many disjoint directed (double) rays
already implies the existence of infinitely many
disjoint directed (double) rays and possible
analogues of Halin's grid theorem. 
Papers 
Carl Bürger
Pascal
Gollin
Karl Heuer
Attila
Joó
Ruben Melcher
Max
Pitz

Normal spanning
trees in uncountable graphs

In a paper from
2001 (JLMS), Diestel and Leader characterised
uncountable graphs that admit a normal spanning
tree through a class of forbidden minors. These
substructures are strongly related to Aronszajn
trees, almost disjoint families and ultrafilters.
Of particular interest in this context are the
socalled aleph_0aleph_1 graphs, or A0A1graphs.
In this project, we
investigate whether these classes of forbidden
minors can be simplified even further. It turns
out that the answer to this problem very much
depends on settheoretic assumptions. Under
Martin's Axiom plus the negation of the Continuum
Hypothesis, the binary trees where we `add’
uncountably many ends are minimal amongst all
A0A1graphs that don’t have NSTs. However, under
CH, it seems as if we have to allow for many
inequivalent forbidden substructuresbut so far
we only know two inequivalent classes through the
work of Diestel and Leader, one related to binary
trees mentioned above, and one related to
ultrafilters on N.
Currently, we investigate
how properties of ultrafilters and graphtheoretic
properties of the corresponding A0A1graphs
interact. Answering a question of Diestel and
Leader, we have constructed, under CH, two
A0A1graphs associated with the same ultrafilter
which are not minors of each other. Our second
major aim is to construct a third class of
A0A1graphs, incomparable with the two already
known classes.

Papers 
Nathan
Bowler
Reinhard
Diestel
Stefan
Geschke
Max
Pitz

Reconstruction of
infinite graphs

The Reconstruction
Problem asks whether a graph is
determined up to isomorphism if we know its
vertexdeleted subgraphs, and the wellknown Reconstruction
Conjecture states that every finite graph
with at least three vertices is in this sense
reconstructible. The analogue for infinite graphs
of the Reconstruction Conjecture is not true in
general. Nevertheless, there are various open
problems about the reconstruction of locally
finite infinite graphs which have remained open
for well over 40 years, most importantly the
HararySchwenkScott conjecture that every locally
finite tree is reconstructible.
Recently, we have
developed a new technique involving promise structures
which made it possible to recursively construct
pairs of nonhomeomorphic graphs which are
reconstructions of each other, leaving enough
degrees of freedom to arrange for various
desirable graphtheoretical properties. Using this
flexible technique we have produced
counterexamples to the HararySchwenkScott
conjecture, and also to many of the remaining open
problems about the reconstruction of locally
finite graphs.

Papers 
Nathan
Bowler
Joshua
Erde
Florian
Lehner
Max
Pitz

Graph symmetries

This project splits
into three parts. In the first two parts we use
graph symmetries to obtain results about the
structure of graphs. The third part studies
symmetry breaking in order to develop a better
understanding of the action of automorphism groups
of locally finite graphs.
The aim in the first part
is to develop a theory for transitive graphs that
can be seen as a graphtheoretical analogue of the
BassSerretheory for groups. First results in
this direction are accessibility results for
transitive graphs.
The second part offers
classifications of graphs and digraphs satisfying
various symmetry assumptions such as homogeneity
and weakenings of this notion:
connectedhomogeneity, sethomogeneity, etc.
The third part deals with
the study of distinguishing numbers. A
distinguishing (vertex or edge) colouring of a
graph is a colouring that no nontrivial
automorphism preserves. The distinguishing number
of a graph is the least number of colours in any
distinguishing colouring. It has been conjectured
that, if every nontrivial automorphism of a
locally finite graph moves infinitely many
vertices, its distinguishing number is 2. We are
tackling this conjecture using methods from
combinatorics, probability theory, and topological
group theory.

Papers

Agelos
Georgakopoulos
Joshua
Erde
Matthias
Hamann
Florian
Lehner
Babak Miraftab
Max
Pitz

Hyperbolic graphs

In this project we
investigate how the intuitive `treelikeness' of
hyperbolic graphs, such as the Cayley graphs of
hyperbolic groups, can be captured and made
precise in graphtheoretic terms.
Partly, we are
considering this question in its full generality.
But we also look at how additional restrictions on
the graphs, e.g. some suitable action of its
automorphism group, contribute to treelikeness.

Papers

Johannes
Carmesin
Agelos Georgakopoulos
Matthias
Hamann

Former
projects
Papers not included above are in:
finite graph minors and connectivity,
graphs with ends (topological),
infinite graphs (general).


