STRUCTURAL-PROPERTIES OF MATROID MATCHINGS

This paper refines Lovasz's duality theory for the linear matroid parity problem by: (1) characterizing a minimum cover in terms of maximum matchings, (2) characterizing maximum matchings in terms of a minimum cover and (3) characterizing critical structures called hypomatchable components. We describe a naturally arising lattice of minimum covers for primitive parity problems and characterize the least and greatest elements in this lattice. For not necessarily primitive parity problems, we introduce a class of minimum covers whose members form a lattice and show that the critical components in the least element of this lattice exhibit a special property called "hypermatchability".