Pluhár András: Friss eredmények hipergráf színezésekkel és játékokkal kapcsolatban |
|
|
|
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