Grzesik, Andrzej and Mikalački, Mirjana and Nagy, Zoltán Lóránt and Naor, Alon and Patkós, Balázset al. - Avoider-enforcer star games

dmtcs:2124 - Discrete Mathematics & Theoretical Computer Science, March 26, 2015, Vol. 17 no. 1 (in progress)
Avoider-enforcer star games

Authors: Grzesik, Andrzej and Mikalački, Mirjana and Nagy, Zoltán Lóránt and Naor, Alon and Patkós, Balázs and Skerman, Fiona

In this paper, we study (1 : b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k≥3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games — the strict and the monotone — and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases fmonF, f-F and f+F, where F is the hypergraph of the game.


Source : oai:HAL:hal-01196868v1
Volume: Vol. 17 no. 1 (in progress)
Section: Combinatorics
Published on: March 26, 2015
Submitted on: July 10, 2013
Keywords: positional games,complete graph,Avoider-Enforcer,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]


Share

Browsing statistics

This page has been seen 24 times.
This article's PDF has been downloaded 43 times.