On matroid intersections

This paper exploits and extends results of Edmonds, Cunningham, Cruse and McDiarmid on matroid intersections. Let r 1 and r 2 be rank functions of two matroids defined on the same set E. For every S ⊂E, let r 12(S) be the largest cardinality of a subset of S independent in both matroids, 0≦k≦r 12(E)-1. It is shown that, if c is nonnegative and integral, there is a y: 2 E →Z + which maximizes {Mathematical expression} and {Mathematical expression}, subject to y≧0, ∀j∈E, {Mathematical expression}. © 1981 Akadémiai Kiadó.