Seminar

# 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.

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.

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU