On winning fast in Avoider-Enforcer games

Publication date 16 June 2010

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

Full work available at URL https://arxiv.org/abs/0910.4402, https://eudml.org/doc/224193, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r56.html

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

zbMATH Keywords

\(k\)-degenerate graph avoider diamond-free graph enforcer extremal graph theory

Mathematics Subject Classification ID

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

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

2 n - 8

moves, being just 6 short of the maximum possible. A diamond-free graph can have at most

d (n) = l c e i l f r a c 3 n - 5 2 c e i l

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.

Review text

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.

Recommendations

Cited in

(6)

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)