The Matroids with the Box Max-Flow Min-Cut Property

Wenan Zang 1, Xujin Chen 2, and Guoli Ding 3
1 Department of Mathematics, University of Hong Kong, Hong Kong, P. R. China
2 Institute of Applied Mathematics, Academia Sinica, Beijing 100080, P. R. China
3 Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA

Abstract

Let $M$ be a matroid and let A be the circuit-element incidence matrix of $M$. We say that $M$ enjoys the max-flow min-cut property if the linear system $A{\bf x} \ge {\bf 1}, \,\, {\bf x} \ge {\bf 0}$ is totally dual integral (TDI), and say that M enjoys the box max-ow min-cut property if the linear system $A{\bf x} \ge {\bf 1}, \,\, {\bf x} \ge {\bf 0}$ is box-totally dual integral (box-TDI). In 1977, Seymour managed to characterize all matroids with the max-flow min-cut property; this far-reaching theorem yields a number of minmax relations in combinatorial optimization. In this talk I shall present a complete characterization of all matroids with the box max-flow min-cut property; our theorem also has many interesting corollaries.