MTA Székház, Nagyterem 1051 Budapest, Széchenyi István tér 9.
Részletek
A szubmoduláris függvények diszkrét optimalizálásban betöltött alapvető szerepére Edmonds mutatott rá (1965–1984), akinek a (poli)matroidokra kidolgozott min-max tételei és algoritmusai egymástól távol fekvő területeken kerültek felhasználásra. E széles körű alkalmazhatóság hátterére világított rá Lovász (1983) azon felismerése, miszerint a szubmoduláris függvények a konvex függvények diszkrét ellenpárjának tekinthetők. A párhuzam egyik első konkrét megjelenése az 1982-ben publikált diszkrét szeparációs tétel, amely szerint, ha az egészértékű p szupermoduláris és b szubmoduláris függvényekre p ≤ b teljesül, akkor elválaszthatók egy egészértékű moduláris függvénnyel.
E korai eredmények jellemzője, hogy lineáris célfüggvények optimalizálására vonatkoznak szubmoduláris függvények által definiált egész poliédereken. 1992-ben Dress és Wenzel bevezette az értékelt („valuated”) matroid fogalmát, amely egy matroidokon definiált diszkrét konkáv függvényt modellez, és kiindulópontul szolgált Murotának egy széles körben alkalmazható új elmélet kidolgozásához.
A jelen előadás az elmúlt öt esztendő idevonatkozó eredményeiről ad áttekintést. Vázoljuk például, hogy a diszkrét konvex megközelítés miképp vezetett el Borradaile egy 2017-es, gráfok „igazságos” erősen összefüggő irányíthatóságára vonatkozó elegáns sejtésének igazolásához. Egy másik frissen feltárt kapcsolat arra világít rá, hogy miképpen lehet inverz kombinatorikus optimalizálási problémákat diszkrét konvex függvények segítségével kezelni. Szó esik olyan új típusú min-max tételekről is, amelyeknél az egész vektorokon felvett minimum nagyobb, mint a valós vektorokon: például ha egy páros gráfnak olyan előírt élszámú részgráfját keressük, melyre a fokszámok négyzetösszege minimális.
