A matroid generalization of theorems of Lewin and Gallai

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: A matroid generalization of theorems of Lewin and Gallai

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798663)