SEMINAR: Groups and Combinatorics: Packing Steiner trees

Groups and Combinatorics Seminar

Irene Pivotto (UWA)

will speak on

Packing Steiner trees

at 1pm Tuesday 2nd of October in MLR2

Abstract: A classic theorem of Nash-Wiliams and Tutte gives necessary and sufficient conditions for a graph to have k pairwise edge-disjoint spanning trees. We will discuss the natural generalization of this problem to trees spanning a distinguished set of vertices (which we refer to as Steiner trees). Finding edge-disjoint spanning trees is a considerably easier problem that finding edge-disjoint Steiner trees. This is due to the fact that spanning trees are bases of the natural matroid associated with a graph, while Steiner trees are not bases of any matroid. We will present a result that provides sufficient conditions for the existence of k edge-disjoint Steiner trees, reducing this problem to finding disjoint bases of a particular matroid. No prior knowledge of matroid theory is required to attend the talk.