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

dmtcs:2124 - Discrete Mathematics & Theoretical Computer Science, March 26, 2015, Vol. 17 no. 1 -
Avoider-enforcer star gamesArticle

Authors: Andrzej Grzesik ORCID1; Mirjana Mikalački ORCID2; Zoltán Lóránt Nagy ORCID3; Alon Naor 4; Balázs Patkós ORCID5,3; Fiona Skerman ORCID6

  • 1 Theoretical Computer Science Department [Krakow]
  • 2 Department of Mathematics and Informatics [Novi Sad]
  • 3 Alfréd Rényi Institute of Mathematics
  • 4 School of Mathematical Sciences [Tel Aviv]
  • 5 Geometric and Algebraic Combinatorics Research Group
  • 6 Department of Statistics [Oxford]

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.

Volume: Vol. 17 no. 1
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]

1 Document citing this article

Consultation statistics

This page has been seen 486 times.
This article's PDF has been downloaded 621 times.