Az alapfeladatban két játékos, az építõ és a romboló választja felváltva egy n-pontú teljes gráf éleit. Adott k számra az Építõ akkor nyer, ha minden pontnál elér legalább n/2-k fokszámot a saját éleibõl, különben a romboló nyer. Ismert (Székely L. ill Beck J.), hogy építõ nyer, ha k > \sqrt{n \log n}, míg romboló nyer, ha k < 0.1 \sqrt{n}. (Az elsõ eredményt bizonyítjuk is, a másodiknak esetleg a gondolatát ismertetjük.)
Felmerül a kérdés, mi érhetõ el egy n-pontú d-reguláris G gráfon játszva? Itt az építõ által elérendõ fokszám természetes alakja d/2 -k. Könnyen látható az építõ nyerése, ha k > \sqrt{d \log n}. Ez nagyon messze lehet a valóságtól, ha n >> d, ugyanis a sejtés k > \sqrt{d \log d}.
Nagyon kevés eredmény van errõl, annyi könnyen látható, hogy építõ nyer, ha k > d/4. Ez motiválhatta a Hefetz-Krivelevich-Stojakovic-Szabó szerzõ négyest a következõ típusú játékokra. Rögzítsük az n és m természetes számokat és egy P monoton gráftulajdonságot. (Utóbbi lehet pl. összefüggõség, minden pont foka legalább egy, van Hamilton kör stb).
Elõször építõ kiválaszt m élt az n-pontú teljes gráf éleibõl (ez lesz a tábla), majd ezeken az éleken játszanak építõ-romboló játékot. Azaz építõ nyer, ha az éleibõl alkotott részgráf P tulajdonságú, míg romboló nyer különben.
Többek közt Hefetz és társai megmutatták, hogy a "minden pont foka legalább egy" tulajdonság esetén építõ nyer, ha m > 10n/7 és romboló nyer, ha m < 11n/8. Fõ eredményként megmutatjuk, hogy az elsõ korlát az éles, azaz romboló nyer, ha m < 10n/7.
Az eredmény közös munka Balogh Józseffel, további részletekért lásd: preprint
Minden érdeklõdõt szeretettel várunk,
Péter