|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Tardos Gábor: A klikk-játékról és a nagy girth-nagy kromatikus számról szóló Erdős-Hajnal sejtésről |
|
|||
|
|
||||
|
||||
| A klikk játékban két játékos közösen épít egy gráfot. A gráf eredetileg üres, majd a két játékos felváltva lép: - Építő hozzáad a gráfhoz egy új csúcsot, azt összeköti az összes többi csúccsal, majd a keletkezett gráf éleit tetszőlegesen két részre bontja. - Romboló a két rész közül az egyikben szereplő összes élet kitörli a gráfból. Építő nyer, ha sikerül egy 100 csúcsú klikket létrehoznia. Romboló célja ezt megakadályozni, vagy legalább addig elodázni, amíg bírja. A véletlen módszer egyik első alkalmazásaként Erdős Pál belátta, hogy léteznek nagy girth-ű nagy kromatikus számú gráfok. Precízebben: tetszőleges pozitív g és k esetén létezik olyan k-kromatikus véges gráf, aminek nincs g-nél rövidebb köre. Hajnal Andrással azt sejtették, hogy nem hogy csak léteznek ilyen gráfok, de minden nagy kromatikus számú gráfban benne vannak: minden g-hez és k-hoz van N, hogy minden N-kromatikus gráfnak van k-kromatikus részgráfja, aminek nincs g-nél rövidebb köre. A g=4 (háromszögmentes) esetet Vojtěch Rödl belátta, nagyobb girth esetén azonban a sejtés nyitott. Tud Építő nyerni a Klikk játékban? Ha igen, hány lépés alatt? És mi köze ennek az Erdős-Hajnal sejtéshez? Ezt próbálom megvilágítani az előadással, amely egy Bartosz Walczakkal és Seth Pettievel közös cikkre épül. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013
