Project
|
Summary
|
Details
|
Contact
|
Homology for
locally finite graphs
|
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
|
Infinite matroids
DFG-gefördert |
Traditionally,
infinite matroids are defined like finite ones,
with the proviso that an infinite set is independent
if and only if all its subsets are independent.
This definition covers infinite-dimensional vector
spaces and the usual cycle matroids of infinite
graphs. It fails to cover more genuinely infinite
notions of independence, such as in Hilbert spaces
or graphs with ends. More fundamentally, it wrecks
duality: such `finitary' infinite matroids do not
have finitary duals.
As duality is at the core
of finite matroid theory and its applications,
Rado asked in 1966 for the development of a theory
of infinite matroids with duality. Such matroids
would have to be potentially non-finitary, and
they would allow for infinite circuits.
Guided by the
Poincaré-type duality found in infinite
graphs with ends, we were able recently to solve
Rado's problem: we found five equivalent sets of
axioms for infinite matroids with duality, in
terms of independence, bases, circuits, closure or
rank, that default to the usual notions when the
matroid is finite or finitary.
Using these axioms, we
are now in a position for the first time to
properly study infinite matroids: to transfer some
of the finite theory to the vast class of
non-finitary infinite matroids (which includes all
the duals of finitary infinite matroids), to study
intrinsic questions such as how infinite matroids
arise as limits of finite ones (an important
potential proof strategy), and to find new
applications to non-finitary structures such as in
analysis.
|
Papers
|
Henning
Bruhn
Reinhard
Diestel
Fabian.Hundertmark
Jan-Oliver Fröhlich
Matthias
Kriesell
Rudi
Pendavingh
Julian Pott
Paul
Wollan |
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
Matthias
Kriesell
Theo Müller
Paul
Wollan
|
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 Menger's theorem in subspaces of |G|, the
existence of a Hamilton circle in 4-connected
planar graphs (with Xingxing Yu), and how to force
a desired minor by density assumptions on |G|. |
Papers
|
Henning
Bruhn
Reinhard
Diestel
Agelos
Georgakopoulos
Maya
Stein |
Hyperbolic graphs
and boundaries
|
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.
Another line of research
is how the homology theory we developed for
locally finite graphs with ends can be recast in
metric terms so that, when boundaries are defined
not as compactifications but as metric
completions, it extends our homology results for
locally finite graphs with ends to spaces like
hyperbolic graphs with boundary, or
non-locally-finite graphs with ends.
|
Papers |
Matthias
Hamann
Agelos
Georgakopoulos
|
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
Fabian Hundertmark
Maya
Stein
|
Graphs and groups
EU-gefördert
|
The aim in this
project is to classify graphs and digraphs
satisfying various symmetry assumptions such as
homogeneity. A main tool in the proofs is the new
tree structure theory in terms of `vertex cuts' of
Dunwoody and Krön, a forerunner of the theory
we developed in our project `Connectivity and tree
structure' cited above.
|
Papers |
Matthias Hamann
Fabian Hundertmark
Bernhard
Krön
Julian Pott
|
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
|
Henning
Bruhn
Reinhard
Diestel
Agelos
Georgakopoulos
Philipp
Sprüssel |
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 |
Reinhard
Diestel
Agelos
Georgakopoulos
Philipp
Sprüssel |
Graph minors and
ubiquity
|
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. Apparently, ubiquity problems are
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
|
Thomas
Andreae
|
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 in general true.
Nevertheless there are various open problems about
the reconstructibility of infinite graphs: for
example, it is not known whether every locally
finite connected infinite graph is
reconstructible. Another challanging problem:
given two infinite trees having (up to
isomorphism) the same collection of vertex-deleted
subgraphs, are these trees necessarily isomorphic?
The goal of the project is to achieve further
progress on the variety of open questions in the
field of reconstruction of infinite graphs.
|
Papers |
Thomas
Andreae |
Metric graph theory
|
|
Papers
|
Hans-Jürgen
Bandelt
|
Heisenberg-Professur:
Diskrete Mathematik
DFG-gefördert
|
This project
focuses on question in extremal and probabilistic
graph theory. Main reserach topics concern the
theory of quasi-random hypergraphs, sufficient
degree conditions for spanning subhypergraphs and
extremal problems in sparse random discrete
structures.
|
Paper |
Mathias
Schacht
|
