Pluhár András: Lassított újraszínezés

címmel tartja meg a kombinatorika szeminárium legközelebbi elõadását.

Rövid leírás: Ha adott egy $X$ halmaz és annak részhalmazainak egy $H$ halmaza, akkor az $(X,H)$ párt hipergráfnak nevezzük. Régi probléma, mikor lehet egy hipergráf pontjait (azaz az $X$ alaphalmazt) úgy színezni két színnel, hogy ne legyen egyszinû él, azaz olyan $A \in H$, amelynek pontjai csak egy színnel színezettek. (Ekkor a színezes jó.) Az $n$-uniform esetet vizsgáljuk részletesen; ekkor minden $A \in H$ él mérete éppen $n$. Erdõs klasszikus eredménye szerint van jó színezés, ha az (uniform) módon választott véletlen színezésekben az egyszínû élek száma nem nagyobb, mint 1. Kb 20 éve Beck József megmutatta, ha ez a várható értek nem nagyobb, mint $c n^{1/3}$, akkor még mindig van jó színezés. Az ötlet ( egy korábbi elõadáson már elhangzott, de itt is érintjuk majd) egy átlagos véletlen színezésnel keletkezett egyszinû halmazok újraszínezése. Nemrégiben Radhakrisnan es Srinivasan rájött, ha az újraszínezést nem egy lépésben, hanem egy folyamat során hajtjuk végre, akkor a korlát tovább javítható: ha a várható érték nem nagyobb, mint $c n^{1/2}$, akkor a hipergráf jól színezhetõ két színnel.

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

Péter