Project

Summary

Details

Contact

Tangletree duality

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. Tangletree 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, so that the highly connected
substructures described by the tangles are found
in nodes, or small subtrees, of this tree. Tangle 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 duality paper
Basic
tangletree paper
All
papers
Carmesin's
thesis

Nathan
Bowler
Johannes Carmesin
Reinhard
Diestel
Joshua Erde
Pascal Gollin
Matthias
Hamann
Fabian Hundertmark
Sahar Lemanczyk 
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 duality 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
Patent

Reinhard Diestel
Pascal Gollin
Jakob Kneip

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
Bowler's
Habil
Carmesin's
thesis
Müller's
thesis
Afzali's
thesis
Fröhlich's
thesis

Hadi
Afzali
Nathan
Bowler
Johannes Carmesin
Reinhard
Diestel
JanOliver Fröhlich
HiuFai Law
Malte Müller
Julian Pott 
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

Graph symmetries

This project splits
into two parts. In the first part we use graph
symmetries to obtain results about the structure
of graphs. The second 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 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
Georgakopoulos's Habil

Agelos Georgakopoulos
Matthias
Hamann
Florian
Lehner
Babak Miraftab
Tim Rühmann

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

Reinhard
Diestel
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
Pott's
thesis

Reinhard
Diestel
Matthias
Hamann
Pascal Gollin
Karl Heuer
Babak Miraftab
Florian
Lehner
Julian Pott
Tim Rühmann
Daniel Weißauer

Homogeneity

The aim of this
project is to classify graphs and digraphs
satisfying various symmetry assumptions such as
homogeneity and weakenings of this notion
(connectedhomogeneity, sethomogeneity, etc.).

Papers
Hamann's
Habil
Pott's
thesis

Matthias
Hamann
Julian Pott

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 
Reinhard Diestel
Nathan
Bowler
Stefan
Geschke
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.

Solution to
Halin's problem
Pott's
thesis

Nathan
Bowler
Johannes Carmesin
Julian Pott

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.

Counterexamples 
Nathan
Bowler
Joshua Erde
Peter Heinig
Florian
Lehner
Max
Pitz

Geometric aspects
of treewidth

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
Malte Müller
Daniel Weißauer

Connectivity vs.
linkability

Our aim in this
project is to use a refined version of the
RobertsonSeymour structure theorem for finite
graphs without a fixed given minor to prove that
(2k+3)connected finite graphs are klinked. This
would be a breakthrough in the area of
linkability.

Structure theorem
Pott's
thesis
Fröhlich's
thesis
Müller's
thesis

Reinhard
Diestel
JanOliver Fröhlich
Theo Müller
Julian Pott

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. 

Pascal Gollin
Peter Heinig
Karl Heuer
Florian
Lehner
