Description
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.