Schriftzug: Fachbereich Mathematik 
  UHH > Fakultäten > MIN-Fakultät > Mathematik > Bereiche > Diskrete Mathematik   STiNE |  KUS-Portal |  Sitemap Suchen Hilfe there is no english version of this page  

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
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. As an example, we have outlined a tangle-based approach to image segmentation (Mona Lisa paper).
   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

Clustering

Image segmentation

Social sciences

Nathan Bowler
Reinhard Diestel
Christian Elbracht
Joshua Erde
Max Teegen
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
Nathan Bowler
Johannes Carmesin
Reinhard Diestel Joshua Erde
Pascal Gollin
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
Ruben Melcher
Max Pitz
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

 
  Seitenanfang  Impressum 2022-09-06, RD