Bapat, R. B.
(1994)
*König's theorem and bimatroids*
Linear Algebra and its Applications, 212-213
.
pp. 353-365.
ISSN 0024-3795

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/0...

Related URL: http://dx.doi.org/10.1016/0024-3795(94)90410-3

## Abstract

König's theorem asserts that the minimal number of lines (i.e., rows or columns) which contain all the ones in a 0-1 matrix equals the maximal 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 graphs. An extension of König's theorem to "mixed matrices" has recently been given by Murota, and it generalizes a determinantal version of the Frobenius-König's theorem obtained earlier by Hartfiel and Loewy. These 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 function of the bimatroid which includes some earlier extensions of König's theorem.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Elsevier Science. |

ID Code: | 78325 |

Deposited On: | 19 Jan 2012 06:32 |

Last Modified: | 19 Jan 2012 06:32 |

Repository Staff Only: item control page