Tutte seminar - Bertrand Guenin

A Survey on Multi-flows in Graphs and Matroids

Abstract: 

In a multi-flow problem we are given a weighted graph where the edges are partitioned into demand and capacity edges. Every edge e is assigned a non-negative value. For a demand edge e, the value indicates the amount of flow required between the endpoints of e, and for a capacity edge e, the value is the amount of flow allowed between the endpoint of that edge. I will discuss sufficient conditions for the existence of an integer or a fractional flow. We will also look at how multi-flow problems generalize to binary matroids and present recent results on some long standing conjectures of Seymour. I will not assume any background in matroid theory.