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
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,
Hi&x1ec7;p Hàn

Combinatorial Optimization


Project
Summary Details
Contact

Polyhedral combinatorics


Hans-Jürgen Bandelt

Biomathematics


Project
Summary Details
Contact

Combinatorial phylogenetics


Hans-Jürgen Bandelt

Genetics


Project
Summary Details
Contact

Archaeogenetics

Papers
Talk: Heidelberg 2006

Hans-Jürgen Bandelt

Quality control of mtDNA data

Papers
Talk: Cologne 2004
Talk: Heidelberg 2006

Hans-Jürgen Bandelt

Uncovering scientific misconduct

Talk: Hyderabad 2006 Hans-Jürgen Bandelt

 
  Seitenanfang  Impressum 2019-03-22, RD