Minimum partition of a matroid into independent subsets
Jack Edmonds · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · 1965
A matroid M is a finit e se t M of e le me nts with a famil y of subsets, calle d inde pe nde nt, s uc h th a t (I) every su bset of an ind e pe nd e nt se t is indepe nde nt, and ( 2) for e ve ry s ubset A of M , all maximal inde pe nd e nt s ub sets of A have th e sa me ca rdinality , calle d th e rank r\A) o f A. It is proved that a matroid ca n be partitione d into as few as k sets, eac h ind e pe nd e nt , if and o nly if e ve ry s ub se t A has cardinality at mos t k .r(A ).