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 min-max
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 straight-forward generalisation
fails as the tree-packing 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
graph-like topological spaces. Infinite gammoids
and infinite oriented matroids have also been
intensively investigated.
The current short-term
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
longer-term research effort, include the Farkas
Lemma for infinite regular matroids and the
infinite matroid intersection conjecture. A
further long-term 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
Ann-Kathrin 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,
Nash-Williams's immersion relations, and the minor
relation. Surprisingly, ubiquity problems turned
out to be closely related to questions of
well-quasi-ordering. 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
non-principal 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
DFG-gefö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
minimum-degree 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 edge-disjoint 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/Nash-Williams tree packing theorem, and of
Fleischner's theorem that the square of a
2-connected finite graph contains a Hamilton
cycle.
Open problems currently
studied include the existence of a Hamilton circle
in 4-connected 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
vertex-deleted subgraphs, and the well-known 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
Harary-Schwenk-Scott 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 non-homeomorphic graphs which are
reconstructions of each other, leaving enough
degrees of freedom to arrange for various
desirable graph-theoretical properties. Using this
flexible technique we have produced
counterexamples to the Harary-Schwenk-Scott
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 graph-theoretical analogue of the
Bass-Serre-theory 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:
connected-homogeneity, set-homogeneity, 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 tree-decomposition
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
tree-decompositions where every part induces a
connected subgraph, so that large distances are
necessarily reflected by size, yielding a notion
of connected
tree-width. 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 tree-decompositions. An
unforeseen by-product of our studies has been a
metric viewpoint of tree-width 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 `tree-likeness' of
hyperbolic graphs, such as the Cayley graphs of
hyperbolic groups, can be captured and made
precise in graph-theoretic 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 tree-likeness.
|
Papers
|
Johannes
Carmesin
Agelos Georgakopoulos
Matthias
Hamann
|
Connectivity vs. linkability
|
Our aim in this
project is to use a refined version of the
Robertson-Seymour structure theorem for finite
graphs without a fixed given minor to prove that
(2k+3)-connected finite graphs are k-linked. This
would be a break-through in the area of
linkability.
|
Structure theorem
Pott's thesis
Fröhlich's thesis
Müller's thesis
|
Reinhard Diestel
Jan-Oliver Fröhlich
Theo Müller
Julian Pott
|
Homology for
locally finite graphs
DFG-gefö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 non-trivial.
The main aim of this
project is to define a singular-type 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
AvH-gefördert
DFG-gefördert
|
One goal in this
project is to develop and apply a canonical
version of the Robertson-Seymour 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
Jan-Oliver 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 k-inseparable
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
tree-decompositions' 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
GIF-gefö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ös-Menger 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
GIF-gefö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|
DFG-gefö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
path-connected. 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 path-connected 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 well-defined, 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
GIF-gefö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 |
