Keeping avoider's graph almost acyclic
In a general Avoider-Enforcer game we have a finite set \(X\) which is called the board of the game, and a subset \(\mathcal{F}\) of the power set of \(X\) called the collection of `losing sets'. The two players alternately pick elements of \(X\) until all of the elements are chosen. The Avoider wins if at the end of this process he did not pick all of the elements of a losing set. Otherwise the Enforcer wins. In the strict \((1:b)\) biased game, the Avoider picks one element at each turn while the Enforcer picks \(b\) elements, except in his last move where the Enforcer might have to pick fewer than \(b\) elements. It turns out that the strict biased game is not always monotone. Although very surprising, it might be the case that the Avoider wins the \((1:b_1)\) game while the Enforcer wins the \((1:b_2)\) game for some \(b_1 > b_2\), see [\textit{D. Hefetz} et al., J. Comb. Theory, Ser. A, No. 5, 114, 840--853 (2007; Zbl 1121.91018)]. For this reason it is also natural to look at the monotone \((1:b)\) game where the Avoider picks at least one element while the Enforcer picks at least \(b\) elements (except possibly in his last move). As its name suggests this game is indeed monotone. In this article, the authors show that in both the strict and the monotone \((1:b)\) biased games, if \(n\) is sufficiently large, \(b \geqslant 200n\log{n}\) and the board is the edge set of \(K_n\), then the Avoider can ensure that his graph can be made acyclic by removing at most one edge. They also show that in the strict game there is a bias \(b\) with \(200n\log{n} \leqslant b \leqslant 201 n\log{n}\) such that the Avoider can ensure that his graph is acyclic. Since an acyclic graph plus at most one edge is planar, 3-colourable and does not contain a \(K_4\) minor, the authors deduce corresponding results for other avoidance games improving previously known bounds.
- A Hamiltonian game on \(K_{n,n}\)
- A matching game
- A Solution of the Shannon Switching Game
- Avoider-Enforcer games
- Avoider-enforcer: the rules of the game
- Biased Positional Games
- Biased positional games for which random strategies are nearly optimal
- Combinatorial Games
- Hamiltonian games
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- Planarity, Colorability, and Minor Games
- Ramsey games
- Remarks on positional games. I
- How long can a graph be kept planar?
- On the odd cycle game and connected rules
- Avoidable paths in graphs
- On the separation conjecture in avoider-enforcer games
- Avoider-Enforcer games
- Waiter-Client and Client-Waiter planarity, colorability and minor games
- Avoider-Enforcer: the rules of the game
- Avoider-forcer games on hypergraphs with small rank
- Avoider-enforcer star games
- Avoidance couplings on non‐complete graphs
- The Avoider-Enforcer game in hypergraphs of rank 3
- Avoider-enforcer: the rules of the game
This page was built for publication: Keeping avoider's graph almost acyclic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260635)
