Bérczi Kristóf: Közös független halmazok pakolása

Az előadáson Kenjiro Takazawa és Yu Yokoi "A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids" c. cikkének eredményeit tekintjük át. A cikkben közös független halmazok pakolásának (két matroid metszetében) olyan speciális eseteit vizsgálják, melyekben a természetesen felmerülő szükséges feltételek egyben elégségesek is a kívánt pakolás létezésére. A bizonyítás g-polimatroidok metszetére épül, és egyben új értelmezését adja Kotlar és Ziv egy korábbi eredményének, mely elégséges feltételt adott k közös független halmaz létezésére.