
Forschungsschwerpunkt
Diskrete Mathematik
Aktuelle
Forschungsprojekte – Current Research Projects (see here for former projects)
Graph
Theory
For guidance on graph theory in general
see R. Diestel, Graph
Theory, Springer GTM173.
Recent papers not specific to any of the projects
below can be found here:
Project 
Summary 
Details 
Contact

Localglobal graph decompositions

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. We believe that we have found a way which offers such studies a possible formal basis.
We show that every finite graph G decomposes canonically into local parts which, between them, form a global structure displayed by a simpler graph H.
Both H and the decomposition of G which it displays depend only on an integer parameter whose choice sets the intended degree of locality. In particular, the structure of H is not imposed on G – as is the case with treedecompositions.
The graph H and the decomposition of G which it displays are obtained as projections of the tangletree structure of a covering of G that reflects its local structure while unfolding its global structure. In this way, the tangle theory from graph minors is brought to bear canonically on arbitrary graphs, which need not be treelike. Since our coverings of finite graphs are usually infinite, it was part of this project to develop the tangle theory of locally finite graphs to meet our needs.
Our theorem extends to locally finite quasitransitive graphs, and in particular to locally finite Cayley graphs. It thus offers a canonical decomposition for finitely generated groups into local parts, whose relative structure is displayed by a graph.

Basic paper

Reinhard Diestel
Raphael Jacobs Paul Knappe
Jan Kurkofka

Abstract separation systems
Applications to clustering, image segmentation, and generally in the empirical sciences

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).
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
All
papers
Clustering
Image segmentation
Social sciences

Sandra Albrechtsen
Nathan
Bowler
Reinhard
Diestel
Joshua
Erde Michael Hermann Hanno von Bergen

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
All
papers on tangletree duality
Basic
treeoftangles paper
All
papers on trees of tangles

Sandra Albrechtsen
Nathan
Bowler
Johannes Carmesin
Reinhard
Diestel Joshua
Erde
Pascal
Gollin

Normal trees, stars and combs: connectivity in infinite graphs

Normal spanning trees are the analogues of depthfirst search trees in infinite graphs, and they are perhaps the most useful structural tool in infinite graph theory.
Their importance arises from the fact that they capture the separation properties of the graph they span, and so in many situations it suffices to deal with the much simpler tree structure instead of the whole graph.
For example, the end space of a graph coincides, even topologically, with the end space of any of its normal spanning trees. However, not every connected graph has a normal spanning tree, and the structure of graphs without normal spanning trees is still not completely understood.
Confirming an old conjecture of Halin, we have recently completed the proof of the forbidden minor characterisation of graphs that have a normal spanning tree. We also have developed new algorithmic methods for building normal spanning trees in just ω many steps, avoiding any unwieldy transfinite constructions.
Our main current aim is now to understand the structure, and also the endspaces, of all graphs, including those that do not admit a normal spanning tree. Remarkably, even here normal trees – not necessarily spanning – turn out to be essential: they can be used to approximate arbitrarily large graphs up to any prescribed error term.
Another line of investigation is to determine how, in a connected graph, a given subset U of the vertices is linked up in the ambient graph. There are two basic ways in which this can happen: by a subdivided star, or by a subdivided comb. In this project we determine the overall structure of the graph relative to U if U is not linked in one, or both, of these ways. These structures can be described in several alternative ways, and normal trees are once more key to their characterizations.

Papers 
Reinhard
Diestel
Jan Kurkofka
Max
Pitz

Former
projects
Recent papers on structural graph theory not included above are in:
graph minors and connectivity,
infinite graphs with ends (topological),
infinite graphs (general).
All papers of structural graph theory group
Extremal and probabilistic graph theory


