Transversals and matroid partition 论文

摘要

In sec ti on 1, transversal Inatroids are assoc iated with "syste ms of di stin ct represe ntatives" (i. e., tra nsversals) and,. more ge nerally, matc hing matroids are associated with mat c hin gs in grap hs . Th e tra nsve rsal matrold s and a th eore m of P. J. Hi ggin s on di sjoint tran sversals of a famil y of se ts , along wIth th e well-known graphIc matrold s a nd so me th eor ems on deco mpos ition of grap hs into fore sts motI~ate som e th eore ms on partitions of ge neral matroid s into inde pe ndent sets. In sec tion 2, th ~ relatIOn s hiP . between tra nsversal result and matroid res ult is illu strated for a s pecial case of lat e r th eo rems. In sectIOn 3, the orems o n tra ns versals are proved usin g network flow s . In sec tions 4 and 5, theore ms on matrold s a re presented whi c h imply various res ults on deco mpo sition into tran sversals 0,1' IIltO forests . In sec tion 6, th e ma tc hin g matro ids are show n to be simpl y the tra nsve rsal matroid s.