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

Abgeschlossene
Forschungsprojekte – Completed Research Projects

Project
Summary
Details
Contact
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
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
Ann-Kathrin Elm
Stefan Geschke
Attila Joó
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
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

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 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
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
Max Pitz
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
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
Connectivity vs. linkability
Our aim in this project is to use a refined version of the Robertson-Seymour structure theorem for finite graphs without a fixed given minor to prove that (2k+3)-connected finite graphs are k-linked. This would be a break-through in the area of linkability.
Structure theorem

Pott's thesis
Fröhlich's thesis
Müller's thesis
Reinhard Diestel
Jan-Oliver Fröhlich
Theo Müller
Julian Pott
Homology for locally finite graphs

DFG-gefö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 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
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
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 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
Alexander Foremny
Fabian Hundertmark
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 Philipp Sprüssel
Agelos Georgakopoulos
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 Reinhard Diestel
Philipp Sprüssel
Agelos Georgakopoulos
Graphs with ends: topological properties of the space |G|

DFG-gefö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 path-connected. 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 path-connected 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 well-defined, 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

GIF-gefö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,
Hiep Hàn


 
  Seitenanfang  Impressum 2024-10-02, RD