The Schrijver system of odd join polyhedra (Q1101352): Difference between revisions

Graphs for which the set of t-joins and t-cuts has ``the max-flow-min-cut property'', i.e. for which the minimal defining system of the t-join polyhedron is totally dual integral, have been characterized by \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 23, 189-222 (1977; Zbl 0375.05022)]. An extension of this problem is to characterize the (uniquely existing) minimal totally dual integral defining system (Schrijver-system, discussed by \textit{A. Schrijver} [Linear Algebra Appl. 38, 27-32 (1981; Zbl 0474.90065)]) of an arbitrary t-join polyhedron. This problem is solved in the present paper. The main idea is to use t-borders, a generalization of t-cuts, to obtain an integer minimax formula for the cardinality of a minimum t-join. (A t-border is the set of edges joining different classes of a partition of the vertex set into t-odd sets.) It turns out that the (uniquely existing) ``strongest minimax theorem'' involves just this notion.