Előző hónap Előző nap Következő nap Következő hónap
Év szerint Hónap szerint Ugrás a hónaphoz

Pluhár András: Friss eredmények hipergráf színezésekkel és játékokkal kapcsolatban

iCal fájl letöltése
Péntek, 8. Március 2013, 10:00

A hatvanas evek elejen bizonyitotta Erdos, hogy egy n-uniform hipergraf
2-szinezheto, ha az elszama 2^{n-1}-t nem haladja meg. Egy veletlen
konstrukcioval pedig azt, hogy van olyan cn^2*2^n elu hipergraf, ami mar
nem 2-szinezheto. Veletlen nelkul nem nagyon volt ismert jo eredmeny,
nemregiben viszont Heidi Gebauer konstrual 2^{n+o(1)} elu, nem ketto
szinezheto n-uniform hipergrafot.

Egyfajta szinezest jelentenek (Picker gyozelme eseten) a Chooser-Picker
jatekok. Itt, a szokasostol elteroen, nem felvaltva veszik a jatekos egy
hiprgraf csucsait, hanem Picker kivesz kettot, majd Chooser elosztaj oket
(egyet megtart, a masik Pickere). Chooser akkor nyer, ha megszerzi a
hipergraf egy teljes elet. Beck Jozsef sejtese szerint Picker nyer, ha
Breaker (rombolo) nyer ugyanazon a hipergrafon.

Fiachra Knox adott egy ellenpeldat; van olyan 15 pontu 3-uniform
hipergraf, amelyre Breker nyer a Maker-Breaker jatekban, de Chooser nyeri
a Chooser-Picker jatekot.

Egy fontos specialis esetben viszont Bednarska-Bzdega (Bzdc{e}ga)
igazolta egy korabbi sejtesunket (Cs-M-P), vagyis ha az Erdos-Selfridge
feltetel teljesul, akkor Picker nyer.

Hely : Farkas terem

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013