Számítástudományi és Információelméleti Tanszék
Témakiíráss
Stabil párosítások és alkalmazásaik
A stabil párosítások elmélete egy közgazdasági-játékelméleti indíttatású probléma nyomán vált ismertté, és lett fontos része számos területnek, mint pl. a kombinatorikus optimalizálás, poliéderes kombinatorika vagy gráfelmélet. Az alapproblema egy ú.n. stabil házassági séma keresese egy olyan modellben, melyben férfiak es nők vesznek reszt, és minden személy egy általa választott preferenciasorrend szerint rendezi az ellentétes neműeket aszerint, hogy mennyire szeretne vele házasságot kötni. Egy házassági séma instabil, ha létezik olyan férfi es nő, akik egymast kölcsönösen előnyösebb partnernek tekintik, mint az aktualis házastársukat. A tétel, mely szerint tetszőleges modellben létezik stabil házassági séma, számos alkalmazással bír a fenti tudományterületeken. A legutóbbi időben sikerült olyan elemi fixponttetelen alapuló megközelítést találni az alapproblémához, mely az egész elméletet új megvilágításba helyezi.
A kutatas célja a fixpontteteles megközelites további alkalmazásainak keresese. Ilyen alkalmazási terület lehet a gráf listaszínezések elmélete, a matroidelmeleten belül a matroidmetszetek és a stabil párosítások kapcsolata, vagy a perfekt gráfok szempontjábol érdekes Berge-Duchet sejtés.
A témának egyelőre nincs az összes alkalmazasi lehetőséget bemutató irodalma, melynek oka részben az, hogy a kutatas eddig több szálon futott. Egy nem mindenre kiterjedo összefoglalás található: Tamás Fleiner: Stable and crossing structures, www.renyi.hu/~fleiner .
Munkanyelv: angol.
Dr. Fleiner Tamás