Towards a proof of Seymour's 1-flowing conjecture

Tuesday, November 7, 2006 - 4:30pm
Skiles 269
Bertrand Guenin
University of Waterloo

The well known max-flow min-cut theorem states that the maximum amount of flow that can be sent from vertex s to a vertex t in a graph (with capacities) is equal to the capacity of smallest cut which separates s and t. While the notion of flows in graphs extends naturally to binary matroids, the max-flow min-cut relation does not hold for binary matroids in general. However, Seymour conjectured that the aforementioned minimax relation holds as long as the binary matroids do not contain any one of three special obstructions. This conjecture if true would generalize many classical results on multi-commodity flows and matchings. Our approach is to try to give a structural characterization of the binary matroids for which the minimax relation holds. I will review known cases of the conjecture and give a brief sketch of our strategy for solving the conjecture. A more technical description of the tools we are developing will be presented on November 10 during the Combinatorics seminar. This is joint work with Irene Pivotto and Paul Wollan.

Refreshments at 4:00PM in Skiles 236