Project

Summary

Details

Contact

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

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

Nathan
Bowler
Johannes
Carmesin
AnnKathrin Elm
Stefan
Geschke
Attila
Joó

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

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
DFGgefördert

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

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
Max Pitz

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

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

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

Homology for
locally finite graphs
DFGgefördert

The cycle space of
a finite graph is the same as its first simplicial
homology group. The first homology of locally
finite graphs, however, is best described by their
topological
cycle space, the space of edge sets that
are sums mod 2 of the edge sets of circles in the
compact topological space G formed by the graph
G and its ends. (See here for how
finite cycle space theory tranfers to locally
finite graphs for this notion, but not for the
traditional cycle space based on finite cycles
only.)
Although it is based on the
topological notion of a circle in G, the
topological cycle space of a graph is not
readily describable in standard homological terms.
We can describe it as a natural quotient of the
first singular homology group of G, but this
quotient is in general nontrivial.
The main aim of this
project is to define a singulartype homology
theory (together with corresponding cohomology)
which, when applied to G, captures exactly the
topological cycle space of G by the
first homology group. Our goal in doing this is
twofold: to make the topological cycle space
accessible to topological methods, with an
intended benefit for the study of graphs, and
conversely to create a framework in which our
results about the topological cycle spaces of
graphs can be generalized to infinite complexes of
higher dimensions.

Papers

Reinhard
Diestel
Philipp
Sprüssel
Agelos
Georgakopoulos

Graph minors and
Hadwiger's conjecture
AvHgefördert
DFGgefördert

One goal in this
project is to develop and apply a canonical
version of the RobertsonSeymour structure theorem
for graphs without a fixed minor. Robertson and
Seymour themselves proved a number of versions,
not easily compatible and not easy to apply. Our
aim is to combine the strengths of the various
versions, plus some additional features, into one
widely applicable structure theorem.
Böhme,
Kawarabayashi, Maharry and Mohar recently
developed a technique applying the structural
descriptions of the finite graphs not
containing a given minor known from the graph
minor theory of Robertson and Seymour to achieve
progress on Hadwiger's conjecture for large graphs
of high connectivity. In this project we aim to
develop those techniques further, based on our
comprehensive structure theorem to be found
before, with the goal of proving a linear
weakening of Hadwiger's conjecture for large
graphs.

Papers

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

Connectivity and
tree structure

Which dense parts
of a graph can be pairwise separated by a system
of nested separations? Such systems organize the
graph into a tree structure. One can show that,
for any fixed integer k, the maximal kinseparable
vertex sets can be pairwise separated in this way.
We are looking into separating other kinds of
substructures too, such as tangles or ends. Our
aim is to unify, and extend, the `canonical
treedecompositions' proposed by Robertson and
Seymour (GM10) with the `vertex cuts' of Dunwoody
& Krön.

Papers 
Johannes Carmesin
Reinhard
Diestel
Alexander Foremny
Fabian Hundertmark

Flows in infinite graphs
GIFgefördert 
This project has two aspects.
Its combinatorial aspect is how to extend
network flow theory for finite graphs to
infinite graphs using methods recently developed
by Aharoni and Berger for their proof of the
ErdösMenger conjecture. Its topological
aspect is to develop a flow theory for locally
finite graphs that ties in with our homology
project for such graphs outlined above. It will
be interesting to see how these approaches
converge or lead to different theories. 
Papers 
Philipp
Sprüssel
Agelos
Georgakopoulos 
Unfriendly partitions
GIFgefördert 
The original Unfriendly
Partition Conjecture claims that every
graph has a vertex partition into two sets such
that every vertex has at least as many
neighbours in the other class as in its own.
This is an easy exercise for finite graphs, and
false for arbitrary uncountable graphs. Its
countable case is one of the classical open
problems in infinite graph theory. We are
studying recursive approaches to existence
proofs. 
Paper 
Reinhard
Diestel
Philipp
Sprüssel
Agelos
Georgakopoulos 
Graphs with ends:
topological properties of the space G
DFGgefördert 
The space G consisting
of an infinite graph G and its ends is a normal
space, which is in general neither compact nor
metrizable. Its connected subsets need not be
pathconnected. The graphs G for which G is compact
or metrizable can be characterized; they include
all locally finite graphs. The connected subsets
of G
that are not pathconnected can also be
characterized; such sets can exist when G is locally
finite, but they cannot be closed in G.

Book
Survey
Papers

Reinhard Diestel
Agelos
Georgakopoulos Philipp
Sprüssel 
Cycle space
theorems in locally finite graphs

Most of the
classical theorems relating the cycle space of a
finite graph to its structural properties (such as
planarity) fail for infinite graphs, even for
locally finite ones. However, if we build the
cycle space of those graphs G not just
from their (finite) cycles but from the edge sets
of the topological circles in their Freudenthal
compactification G, allowing infinite sums when
they are welldefined, we obtain a larger space
that performs much better. This project aims to
assess to what extent this new topological cycle
space can assume the structural role we
have come to expect of the cycle space of a graph.
So far, the
evidence has been overwhelmingly positive.
Theorems found include infinite versions of the
Tutte/Kelmans planarity criterion, of Mac Lane's
theorem, and of plane duality and Whitney's
theorem. As with a finite graph, the topological
cycle space is generated by its peripheral cycles,
and by its geodesic cycles, as long as the edge
lengths chosen give rise to a metric inducing the
existing topology on G.
A major open conjecture
is that a set of edges lies in the cycle space of
G if and
only if induces even degrees at all vertices and
ends. (End degrees can be infinite in locally
finite graphs; their parity was defined by Bruhn
and Stein.) Other open problems currently
investigated concern the topological bicycle space of G, the
intersection of its topological cycle space and
its cut space.

Survey
Papers

Henning Bruhn
Reinhard
Diestel
Agelos
Georgakopoulos
Philipp
Sprüssel
Maya
Stein

Menger's theorem
for infinite graphs with ends

Menger's theorem,
in the form suggested by Erdös for infinite
graphs, is proved for certain graphs with ends,
including all countable graphs. This means that
the sets of points to be linked may contain a
mixture of vertices and ends. The linkage is made
up of paths – rays or double rays in the case of
linking ends – or, alternatively, arcs in the
Freudenthal compactification of the graph. 
Papers

Henning Bruhn
Reinhard
Diestel
Maya
Stein 
Ramsey theory and
hypergraph regularity
GIFgefördert

Ramsey theory
deals with the existence of order within chaos.
The basic paradigm is that when an ordered object
is partitioned into finitely many parts at least
one of these parts will contain an ordered
substructure. The classical basic example is that
in any finite coloring of the edges of a
sufficiently large complete graph one will find a
relatively large monochromatic complete subgraph.
In this project we study thresholds of Ramsey
properties in random hypergraphs and in random
subsets of the integers.

Paper 
Mathias
Schacht
Yury Person,
Hiep Hàn 