In the Avoider-Enforcer game on the complete graph $K_n$, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property $\mathcal{ P}$, Enforcer wins the game if Avoider's graph has the property $\mathcal{ P}$. An important parameter is $\tau_E({ \cal P})$, the smallest integer $t$ such that Enforcer can win the game against any opponent in $t$ rounds. In this paper, let $\mathcal{ F}$ be an arbitrary family of graphs and $\mathcal{ P}$ be the property that a member of $\mathcal{ F}$ is a subgraph or is an induced subgraph. We determine the asymptotic value of $\tau_E(\mathcal{ P})$ when $\mathcal{ F}$ contains no bipartite graph and establish that $\tau_E(\mathcal{ P})=o(n^2)$ if $\mathcal{ F}$ contains a bipartite graph. The proof uses the game of JumbleG and the Szemer\'edi Regularity Lemma.
Categories: math.CO