Pluhár András: Hipergráfok újraszínezése
A hipergráf 2-színezhetõség egy klasszikus kombinatorikai probléma; Bernstein már foglalkozott vele, majd Erdõs a valószínûségszámítási módszer erejét illusztrálta vele. Ha adott egy X alaphalmaz, és X részhalmazainak egy H halmaza, akkor kérdés, van-e olyan f: X --> {0,1} függvény, amely nem konstans H egyetlen elemén sem. A probléma algoritmikus szempontból nagyon nehéz (NP-teljes), a véletlen megközelítés az alábbit adja: színezzük X elemeit (egymástól függetlenül, egyforma valószinûséggel) két színnel, s ha az egyszínû halmazok száma kisebb, mint 1, akkor van jó színezés. Speciális hipergráfokra (ún. n uniform esetben) Beck József 1978-ban megjavította ezt egy ``újraszínezésí' ötlettel, s megmutatta, hogy van jó színezés még akkor is, ha az egyszínû halmazok várható száma konstans * köbgyök n. Egy algebrai beágyazási probléma a következõ színezés vizsgálatat motiválja: rögzítsünk k db színt (1,...,k) és színezzük úgy X halmazt, hogy minden H-beli részhalmazban forduljon elõ _minden_ szín 1-tõl k-ig. Megmutatjuk, hogy Beck ötlete általanosítható erre az esetre, többé-kevésbé nyilvánvalóan.
Minden érdeklõdõt szeretettel várunk.
Péter