Tanszékcsoporti szeminárium

Bár a szub- és szupermoduláris függvények tudatos használata már a múlt század első felében elkezdődött, igazi jelentőségükre csak a hetvenes évektől fogva derült fény. Az alkalmazhatóság mögött egy meglepő analógia áll: a szubmoduláris függvények olyasféle szerepet játszanak a diszkrét optimalizálásban, mint amilyent a konvex függvények játszanak a folytonosban. A konvex és konkáv függvények analízisből közismert lineáris függvénnyel történő elválaszthatóságanak mintájára érvényes a diszkrét szeparációs tétel, amely szerint, ha p és b egészértékű szuper- illetve szubmoduláris függvény, melyekre p <= b, akkor elválaszthatók egy egészértékű moduláris függvénnyel. E tételnek a párosításokra vonatkozó klasszikus Hall tétel azonnali következménye, de segítségével például meghatározható, hogy egy gráfnak mikor létezik k-élösszefüggő irányítása, amely ráadásul minden pontban megadott be-fok korlátoknak tesz eleget.

1990-ig kidolgozásra kerültek azok a területek, amelyekben a költséges optimalizálási feladatok is szépen kezelhetők, például, hogy miként lehet egy irányított gráf legolcsóbb olyan részgráfját kiszámítani, amelyben egy megadott gyökérpontból minden más pontba vezet k élidegen út. A kilencvenes években a szubmoduláris függvényeknek egészen újfajta felhasználási lehetőségeire derült fény, ahol az általános költséges probléma már NP-teljes, de az alapfeladatot mégis eredményesen lehet kezelni. Az előadásban vázolom ezeket az alkalmazásokat, melyek között olyan távolállónak tetsző következmények vannak, mint Győri nehéz poliomino-fedési tételének kiterjesztése, vagy az irányított gráfok optimális összefüggőség növelésének megoldása. Bemutatok néhány egészen friss alkalmazást is, például azon be- és ki-fok sorozatok jellemzését, melyekhez létezik k-összefüggő egyszerű irányított gráf.