On winning fast in Avoider-Enforcer games (Q976704)

Summary: We analyze the duration of the unbiased Avoider-Enforcer game for three basic positional games. All the games are played on the edges of the complete graph on \(n\) vertices, and Avoider's goal is to keep his graph outerplanar, diamond-free and \(k\)-degenerate, respectively. It is clear that all three games are Enforcer's wins, and our main interest lies in determining the largest number of moves Avoider can play before losing. Extremal graph theory offers a general upper bound for the number of Avoider's moves. As it turns out, for all three games we manage to obtain a lower bound that is just an additive constant away from that upper bound. In particular, we exhibit a strategy for Avoider to keep his graph outerplanar for at least \(2n-8\) moves, being just 6 short of the maximum possible. A diamond-free graph can have at most \(d(n)= \lceil\frac{3n-4}{2}\rceil\) edges, and we prove that Avoider can play for at least \(d(n)-3\) moves. Finally, if \(k\) is small compared to \(n\), we show that Avoider can keep his graph \(k\)-degenerate for as many as \(e(n)\) moves, where \(e(n)\) is the maximum number of edges a \(k\)-degenerate graph can have.