Thesis supervisor: Tamás Fleiner
Location of studies (in Hungarian): Számítástudományi és Információelméleti Tanszék Abbreviation of location of studies: SZIT
Description of the research topic:
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 alapprobléma egy ú.n. stabil házassági séma keresése egy olyan modellben, melyben férfiak es nők vesznek részt, é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 egymást kölcsönösen előnyösebb partnernek tekintik, mint az aktuális 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 fixponttételen alapuló megközelítést találni az alapproblémához, mely az egész elméletet új megvilágításba helyezi.
A kutatás célja a fixponttételes megközelités további alkalmazásainak keresése. Ilyen alkalmazási terület lehet a gráf listaszínezések elmélete, a matroidelméleten 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 alkalmazási lehetőséget bemutató irodalma, melynek oka részben az, hogy a kutatás eddig több szálon futott. Egy nem mindenre kiterjedő összefoglalás található: Tamás Fleiner: Stable and crossing structures, http://www.renyi.hu/~fleiner .
Number of students who can be accepted: 1
Deadline for application: 2018-07-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
