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 games

Authors: Andrzej Grzesik ORCID-iD1; Mirjana Mikalački ORCID-iD2; Zoltán Lóránt Nagy ORCID-iD3; Alon Naor 4; Balázs Patkós ORCID-iD5,3; Fiona Skerman ORCID-iD6

  • 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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0806.0280
Source : ScholeXplorer IsRelatedTo DOI 10.1007/s00373-009-0870-8
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0806.0280
  • 10.1007/s00373-009-0870-8
  • 10.1007/s00373-009-0870-8
  • 0806.0280
  • 10.48550/arxiv.0806.0280
Fast Winning Strategies in Avoider-Enforcer Games

Consultation statistics

This page has been seen 323 times.
This article's PDF has been downloaded 522 times.