×

On winning fast in Avoider-Enforcer games. (English) Zbl 1192.91037

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.

MSC:

91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS