A matroid generalization of theorems of Lewin and Gallai (Q798663): Difference between revisions

Let M be a matroid whose ground set E is partitioned into 2-element blocks. A subset of E is a parity set if, whenever it contains one member of a block, it contains both members of the block. In this note the authors prove that if I is a maximal independent parity set in M and \(J^*\) is a maximal independent parity set in the restriction of \(M^*\) to E-I, then the number of elements that must be added to I to give a basis for M equals the number of elements that must be added to \(J^*\) to give a basis for \(M^*\). The authors then show that this theorem is a matroid generalization of results of \textit{T. Gallai} [Ann. Univ. Sci. Budapest, Rolando Eötvös, Sect. Math. 2, 133-138 (1959; Zbl 0094.361)] and \textit{M. Lewin} [Discrete Math. 5, 283-285 (1973; Zbl 0261.05124)] that relate maximum matchings and minimum coverings in graphs.