2009/10/22 by János Barát, Barát, János, Miloš Stojaković +1
Mathematics · #91A24 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:91A24
paper · pdf · doi:10.48550/arxiv.0910.4402
arxiv created 2009/10/22 · arxiv updated 2009/12/01
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(3n-5)/(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.