KONIGS THEOREM AND BIMATROIDS

Konig's theorem asserts that the minimal number of lines (i.e., rows o f columns) which contain all the ones in a 0-1 matrix equals the maxim al number of ones in the matrix no two of which are on the same line. The theorem occupies a central place in the theory of matchings in gra phs. An extension of Konig's theorem to ''mixed matrices'' has recentl y been given by Murota, and it generalizes a determinantal version of the Frobenius-Konig theorem obtained earlier by Hartfiel and Loewy. Th ese results are generalized. We consider the setup in which there are two finite sets X and Y and a bimatroid (or linking system) defined on the pair (X, Y). We then prove a minimax theorem for the rank functio n of the bimatroid which includes some earlier extensions of Konig's t heorem.