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


Forschungsschwerpunkt Diskrete Mathematik

Abgeschlossene
Forschungsprojekte – Completed Research Projects

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


 
  Seitenanfang  Impressum 2013-02-20, wwwmath (JMD)