On winning fast in Avoider-Enforcer games

zbMATH Open1192.91037arXiv0910.4402MaRDI QIDQ976704FDOQ976704

Authors: János Barát, Miloš Stojaković 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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)=lceilfrac3n-52ceil$ 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.

Full work available at URL: https://arxiv.org/abs/0910.4402

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Fast winning strategies in avoider-enforcer games
• On avoider-enforcer games
• On the separation conjecture in avoider-enforcer games
• Winning fast in biased maker-breaker games
• Winning fast in fair biased maker-breaker games
• On strong avoiding games
• Fast strategies in biased Maker-Breaker games
• Fast winning strategies in maker-breaker games
• Avoider-Enforcer games
• Fast strategies in Waiter-Client games

zbMATH Keywords

extremal graph theorydiamond-free graph\(k\)-degenerate graphavoiderenforcer

Mathematics Subject Classification ID

Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cited In (5)

• Fast winning strategies in avoider-enforcer games
• How long can a graph be kept planar?
• Sharp thresholds for half-random games. II
• Winning fast in biased maker-breaker games
• On avoider-enforcer games

This page was built for publication: On winning fast in Avoider-Enforcer games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976704)