Orientations of infinite graphs
Graphs, Hypergraphs, and Computing
27 February 15:30 - 16:30
Carsten Thomassen - Technical University of Denmark, DTU
In 1960 Nash-Williams proved that every 2k-edge-connected finite graph has a k-arc-connected orientation. More precisely, every edge can be given a direction such that every cut has at least k arcs (directed edges) in each direction.
In 1989 I conjectured that the same result holds for infinite graphs if we replace the edge-connectivity 2k by a larger edge-connectivity f(k). In this talk I will discuss the recent proof of this conjecture.
The weaker version of Nash-Williams' theorem that every 4k-edge-connected finite graph has a k-arc-connected orientation follows immediately from the theorem of Tutte and Nash-Williams from 1961 (and generalized to matroids by Edmonds in 1965) that every 4k-edge-connected finite graphs has 2k pairwise edge-disjoint spanning trees. But this does not extend to infinite graphs. Indeed, there is no finite edge-connectivity guaranteeing an infinite graph to have two edge-disjoint spanning trees, as proved in 1989 by Aharoni and myself.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU