A következő (XI. 16. péntek, 10:00, Farkas-terem) kombinatorika szeminárium előadása

Pluhár András: Párosítások, hipergráf színezés és játékok

A hipergráfokon természetes játékok definiálhatók, a játékosok a pontokat választják és egy teljes élt kívánnak elfoglalni. Ilyen pl a tic-tac-toe, az amőba, hex stb.

A párosítások és a belőlük nyerhető párosítási stratégiák nagyon fontosak a kombinatorikus játékok elméletében. Az esetek nagy részében persze jóval gyengébb eredményeket adnak, mint az optimális játek, ami - ha színezésre akarunk használni egy döntetlen végeredményt - szintén gyengébb, mint a hipergráf kromatikus számának egyéb becslése.

A párosítási stratégiák lehetséges kiterjesztéseit vizsgáljuk meg, ahol nem mezők, hanem a tábla nagyobb darabjait rendeljük egymáshoz. Ezek egyrészt heurisztikákat adnak az eredeti játék eredményére, másrészt egy hierarchiát feszítenek a párosítások és a "végső párosítás" a jó színezések kózt.

Minden érdeklődőt szeretettel várunk,

Péter