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 |
