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

<P><CENTER>
Pluhár András: 
<B>Friss eredmények hipergráf színezésekkel és játékokkal
kapcsolatban</B>
</CENTER>

<P>
A hatvanas évek elején bizonyította Erdős, hogy egy n-uniform hipergráf
2-színezhető, ha az élszáma 2<SUP>n-1</SUP>-t nem haladja meg. Egy véletlen
konstrukcióval pedig azt, hogy van olyan cn<SUP>2</SUP>2<SUP>n</SUP> 
élű hipergráf, ami már
nem 2-színezhető. Véletlen nélkül nem nagyon volt ismert jó eredmény,
nemrégiben viszont Heidi Gebauer konstruált 2<SUP>n+o(1)</SUP>
élű, nem kettő
színezhető n-uniform hipergráfot.

<P>
Egyfajta színezést jelentenek (Picker győzelme esetén) a Chooser-Picker
játékok. Itt, a szokásostól eltérően, nem felváltva veszik a játékos 
egy
hipergráf csúcsait, hanem Picker kivesz kettőt, majd Chooser elosztja őket
(egyet megtart, a másik Pickeré). Chooser akkor nyer, ha megszerzi a
hipergráf egy teljes élet. Beck József sejtése szerint Picker nyer, ha
Breaker (romboló) nyer ugyanazon a hipergráfon.

<P>
Fiachra Knox adott egy ellenpéldát; van olyan 15 pontú 3-uniform
hipergráf, amelyre Breaker nyer a Maker-Breaker játékban, de Chooser nyeri
a Chooser-Picker játékot.

<P>
Egy fontos speciális esetben viszont Bednarska-Bzdega (Bzd\c{e}ga)
igazolta egy korábbi sejtesünket (Cs-M-P), vagyis ha az Erdős-Selfridge
feltétel teljesül, akkor Picker nyer.

<P>
Minden érdeklődőt szeretettel várunk,

<P>
Péter