On the separation conjecture in Avoider-Enforcer games

Abstract

Given a fixed graph $H$ with at least two edges and positive integers $n$ and $b$, the strict $(1:b)$ Avoider-Enforcer $H$-game, played on the edge set of $K_n$, has the following rules: In each turn Avoider picks exactly one edge, and then Enforcer picks exactly $b$ edges. Avoider wins if and only if the subgraph containing her/his edges is $H$-free after all edges of $K_n$ are taken. The lower threshold of a graph $H$ with respect to $n$ is the largest $b_0$ for which Enforcer has a winning strategy for the $(1:b)$ $H$-game played on $K_n$ for any $b\le b_0$, and the upper threshold is the largest $b$ for which Enforcer wins the $(1:b)$ game. The separation conjecture of Hefetz, Krivelevich, Stojaković and Szabó states that for any connected $H$, the lower threshold and the upper threshold of the Avoider-Enforcer $H$-game played on $K_n$ are not of the same order in $n$. Until now, the conjecture has been verified only for stars, by Grzesik, Mikalački, Nagy, Naor, Patkos and Skerman. We show that the conjecture holds for every connected graph $H$ with at most one cycle (and at least two edges), with a polynomial separation between the lower and upper thresholds. We also prove an upper bound for the lower threshold of any graph $H$ with at least two edges, and show that this bound is tight for all graphs in which each connected component contains at most one cycle. Along the way, we establish number-theoretic tools that might be useful for other problems of this type.

The paper is reorganized