|
|
Forschungsschwerpunkt
Diskrete Mathematik
Aktuelle
Forschungsprojekte – Current Research Projects (see here for former projects)
Graph
Theory
For guidance on graph theory in general
see R. Diestel, Graph
Theory, Springer GTM173.
Recent papers not specific to any of the projects
below can be found here:
| Project |
Summary |
Details |
Contact
|
Local-global graph decompositions
|
The question to what extent graph invariants – the chromatic number, say, or connectivity – are of local or global character, and how their local and global aspects interact, drives much of the research in graph theory both structural and extremal. We believe that we have found a way which offers such studies a possible formal basis.
We show that every finite graph G decomposes canonically into local parts which, between them, form a global structure displayed by a simpler graph H.
Both H and the decomposition of G which it displays depend only on an integer parameter whose choice sets the intended degree of locality. In particular, the structure of H is not imposed on G – as is the case with tree-decompositions.
The graph H and the decomposition of G which it displays are obtained as projections of the tangle-tree structure of a covering of G that reflects its local structure while unfolding its global structure. In this way, the tangle theory from graph minors is brought to bear canonically on arbitrary graphs, which need not be tree-like. Since our coverings of finite graphs are usually infinite, it was part of this project to develop the tangle theory of locally finite graphs to meet our needs.
Our theorem extends to locally finite quasi-transitive graphs, and in particular to locally finite Cayley graphs. It thus offers a canonical decomposition for finitely generated groups into local parts, whose relative structure is displayed by a graph.
|
Basic paper
All papers
|
Tara Abrishami
Reinhard Diestel
Raphael Jacobs
Paul Knappe
Jan Kurkofka
|
Abstract separation systems
Applications to clustering, image segmentation,
and generally in the empirical sciences
|
The properties of
tangles and the separations distinguishing them
that are needed for the tangle-tree 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. They can help to find unknown ways of thinking or of behaviour in the social sciences and economics. See the book.
The abstract theory can also be
re-applied 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 tangle-tree duality theory
for infinite graphs and matroids from this theory
of profinite abstract separation systems.
|
Basic paper
All papers
Applying tangles
Book
Software
|
Sandra Albrechtsen
Nathan
Bowler
Reinhard
Diestel
Joshua
Erde
Michael Hermann
Hanno von Bergen
|
Tangles and trees
|
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
low-order separations towards it.
We study two types of
tangle theorems. Tree-of-tangles 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
tree-like way, the tree of tangles, so that the
highly connected substructures described by the
tangles are found in nodes, or small subtrees, of
this tree. Tangle-tree 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 non-existence 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 - tangle-like - tree-width duality
theorem for finite graphs, a canonical tangle-tree
theorem for finite matroids, and a combination of
both types of theorem in which those parts of a
tangle-distinguishing tree-decomposition that are
not home to a tangle are further refined by a
tree-decomposition that witnesses the absence of a
tangle in that part.
|
Basic
tangle-tree duality paper
All
papers on tangle-tree duality
Basic
tree-of-tangles paper
All
papers on trees of tangles
|
Sandra Albrechtsen
Nathan
Bowler
Johannes Carmesin
Reinhard
Diestel Joshua
Erde
Pascal
Gollin
|
Coarse graph theory
|
We aim to understand the global geometric structure of a graph, or of graphs with some given property. Our perspective revolves around the concept of quasi-isometry.
Roughly speaking, two graphs are quasi-isometric if their large-scale geometry coincides: if they look
similar when viewed from a distance.
For example, quasi-isometries provide a formal basis for asking when graphs have a large-scale geometry that is essentially simpler than the graphs themselves.
In structural graph theory, graph properties are often characterized by an exclusion of substructures, e.g. of certain minors.
Excluding more minors then yields a more restrictive property, whose graphs may have a simpler structure.
The large-scale geometry of graphs can similarly be restricted by excluding minors whose models must occur in them at a large scale.
Such substructures are known as fat minors. We can then ask, for example, what can be said about the large-scale geometry of graphs excluding certain graphs as fat minors.
|
Papers |
Sandra Albrechtsen
Matthias Hamann
Paul Knappe
|
Normal trees, stars and combs: connectivity in infinite graphs
|
Normal spanning trees are the analogues of depth-first search trees in infinite graphs, and they are perhaps the most useful structural tool in infinite graph theory.
Their importance arises from the fact that they capture the separation properties of the graph they span, and so in many situations it suffices to deal with the much simpler tree structure instead of the whole graph.
For example, the end space of a graph coincides, even topologically, with the end space of any of its normal spanning trees. However, not every connected graph has a normal spanning tree, and the structure of graphs without normal spanning trees is still not completely understood.
Confirming an old conjecture of Halin, we have recently completed the proof of the forbidden minor characterisation of graphs that have a normal spanning tree. We also have developed new algorithmic methods for building normal spanning trees in just ω many steps, avoiding any unwieldy transfinite constructions.
Our main current aim is now to understand the structure, and also the endspaces, of all graphs, including those that do not admit a normal spanning tree. Remarkably, even here normal trees – not necessarily spanning – turn out to be essential: they can be used to approximate arbitrarily large graphs up to any prescribed error term.
Another line of investigation is to determine how, in a connected graph, a given subset U of the vertices is linked up in the ambient graph. There are two basic ways in which this can happen: by a subdivided star, or by a subdivided comb. In this project we determine the overall structure of the graph relative to U if U is not linked in one, or both, of these ways. These structures can be described in several alternative ways, and normal trees are once more key to their characterizations.
|
Papers |
Reinhard
Diestel
Jan Kurkofka
Max
Pitz
|
Infinite directed
graphs
|
Infinite directed graphs are far less
understood than infinite undirected graphs. We work on structural problems about infinite digraph that are motivated either by existing theorems for graphs
or which arise solely for digraphs.
One problem that has no counterpart
for graphs concerns the ends of digraphs. Unlike in the case of graphs, these come equipped
with a natural ordering. But not much is known about this ordering. In particular, we do not know which orders can arise in this way.
Further problems include directed
analogues of Halin's grid theorem, and problems concerning spanning
arborescences. One prominent problem that does not obviously involve ends concerns the ubiquity of double rays: if a digraph contains unboundedly many disjoint double rays all whose edges are oriented in the same direction, does it then contain infinitely many disjoint such double rays? |
Papers |
Matthias
Hamann
Attila
Joó
Max
Pitz
Florian Reich
|
Former
projects
Recent papers on structural graph theory not included above are in:
graph minors and connectivity,
infinite graphs with ends (topological),
infinite graphs (general).
All papers of structural graph theory group
Extremal and probabilistic graph theory
|
|
|
