Project

Summary

Details

Contact

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,
Hi&x1ec7;p Hàn 