   UHH > Fakultäten > MIN-Fakultät > Mathematik > Bereiche > Diskrete Mathematik STiNE |  KUS-Portal |    Forschungsschwerpunkt Diskrete Mathematik

Aktuelle Forschungsprojekte – Current Research Projects (former projects)

Graph Theory

For guidance on graph theory in general see R. Diestel, Graph Theory, Springer GTM173. Our current research projects are as follows:

Project
Summary
Details
Contact
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 two-fold. 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

Basic tree-of-tangles paper

All papers
Nathan Bowler
Johannes Carmesin
Reinhard Diestel Joshua Erde
Pascal Gollin
Matthias Hamann
Daniel Weißauer
Abstract separation systems, with applications to clustering and image segmentation
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), and have are in touch with the IT industry about implementations of this approach.
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
Mona Lisa paper
All papers

Patent
Nathan Bowler
Reinhard Diestel
Christian Elbracht
Joshua Erde
Jakob Kneip
Max Teegen
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
Reinhard Diestel
Ann-Kathrin Elm
Stefan Geschke
Hendrik Heine
Hiu-Fai Law
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
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
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
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
Daniel Weißauer
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
Normal spanning trees in uncountable graphs
In a paper from 2001 (JLMS), Diestel and Leader characterised uncountable graphs that admit a normal spanning tree through a class of forbidden minors. These substructures are strongly related to Aronszajn trees, almost disjoint families and ultrafilters. Of particular interest in this context are the so-called aleph_0-aleph_1 graphs, or A0A1-graphs.
In this project, we investigate whether these classes of forbidden minors can be simplified even further. It turns out that the answer to this problem very much depends on set-theoretic assumptions. Under Martin's Axiom plus the negation of the Continuum Hypothesis, the binary trees where we `add’ uncountably many ends are minimal amongst all A0A1-graphs that don’t have NSTs. However, under CH, it seems as if we have to allow for many inequivalent forbidden substructures---but so far we only know two inequivalent classes through the work of Diestel and Leader, one related to binary trees mentioned above, and one related to ultrafilters on N.
Currently, we investigate how properties of ultrafilters and graph-theoretic properties of the corresponding A0A1-graphs interact. Answering a question of Diestel and Leader, we have constructed, under CH, two A0A1-graphs associated with the same ultrafilter which are not minors of each other. Our second major aim is to construct a third class of A0A1-graphs, incomparable with the two already known classes.
Papers Nathan Bowler
Reinhard Diestel
Stefan Geschke
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
Babak Miraftab
Max Pitz
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
Former projects

Papers not included above are in: finite graph minors and connectivity, graphs with ends (topological), infinite graphs (general).  Impressum 2019-07-16, RD