Leírás
Jól ismert, hogy k éldiszjunkt feszítőfenyő létezésének kérdése megfogalmazható közös bázis létezésével két matroidban (melyek közül az egyik egy partíciós matroid, a másik a grafikus matroid k-szorosa). Frank András (majd később Bernáth Attila és Király Tamás) észrevette, hogy amennyiben a partíciós matroidot tetszőleges olyan M_2 matroidra cseréljük az éleken, mely előáll az egyes csúcsokba belépő éleken adott tetszőleges matroidok direkt összegeként, akkor Edmonds fenyőtételének egy olyan általánosítását kapjuk, melyben olyan éldiszjunkt feszítőfenyőket keresünk, melyek élhalmaza független M_2-ben. A matroid metszet irányú megközelítéssel könnyen adható a feladat súlyozott változatára is polinomiális algoritmus.
Edmonds fenyőtételének számos általánosítása lett ismert az utóbbi időben, melyek közös pontja az, hogy ezekben a gyökereken adott egy M_1 matroid és a cél az egyes csúcsokat fedő fenyők gyökereinek minél nagyobb méretű M_1-ben független halmaz volta.
Az előadásban bemutatom, hogy hogyan fogalmazhatóak meg a fenti feladatok matroid metszet feladatként, hogyan vezethető be ennek a segítségével (a fenti mintára) további függetlenségi feltétel az éleken, és hogyan kapható polinomiális algoritmus a feladat súlyozott változatára is. A megoldáshoz egy új típusú matroidra van szükség, melyet egy párhalmazokon értelmezett metszőn szubmoduláris függvény segítségével definiálunk.
Az eredmények Szigeti Zoltánnal és Shin-ichi Tanigawával közösek.