Keeping avoider's graph almost acyclic (Q2260635)

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.