Graph Theory Seminar - Irene Pivotto

Title: Packing Steiner trees

Abstract: A classic theorem of Nash-Williams 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 a matroid, while Steiner trees are not. 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.