Avoider-forcer games on hypergraphs with small rank
The electronic journal of combinatorics, Tome 21 (2014) no. 1
We study biased $(a:f)$ Avoider-Forcer games played on hypergraphs, in the strict and monotone versions. We give a sufficient condition for Avoider's win, useful in the case of games on hypergraphs whose rank is smaller than $f$. We apply this result to estimate the threshold bias in Avoider-Forcer $(1:f)$ games in which Avoider is trying not to build a copy of a fixed graph $G$ in $K_n$. We also study the $d$-degree $(1:f)$ game in which Avoider's aim is to avoid a spanning subgraph of the minimal degree at least $d$ in $K_n$. We show that the strict 1-degree game has the threshold which is the same as the threshold of the Avoider-Forcer connectivity game.
DOI :
10.37236/3095
Classification :
91A43, 91A46, 91A05, 05C57, 05C65
Mots-clés : combinatorial game, avoider-forcer game, avoider-enforcer game
Mots-clés : combinatorial game, avoider-forcer game, avoider-enforcer game
Affiliations des auteurs :
Małgorzata Bednarska-Bzdęga 1
@article{10_37236_3095,
author = {Ma{\l}gorzata Bednarska-Bzd\k{e}ga},
title = {Avoider-forcer games on hypergraphs with small rank},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3095},
zbl = {1305.91048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3095/}
}
Małgorzata Bednarska-Bzdęga. Avoider-forcer games on hypergraphs with small rank. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3095
Cité par Sources :