Sách On winning fast in Avoider-Enforcer games

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.