On the Separation Conjecture in Avoider-Enforcer Games

0494643 - ÚI 2020 US eng J - Journal Article
Bednarska-Bzdega, M. - Ben-Eliezer, O. - Gishboliner, L. - Tran, Tuan
On the Separation Conjecture in Avoider-Enforcer Games.
Journal of Combinatorial Theory. B. Roč. 138, September (2019), s. 41-77. ISSN 0095-8956. E-ISSN 1096-0902
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
OECD category: Pure mathematics
Impact factor: 1.306, year: 2019
https://arxiv.org/abs/1709.09065

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 Kn, 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 Kn are taken. The lower threshold of a graph H with respect to n is the largest b0 for which Enforcer has a winning strategy for the (1:b) H-game played on Kn for any b≤b0, and the upper threshold is the largest b for which Enforcer wins the (1:b) game. The separation conjecture of Hefetz, Krivelevich, Stojakovi\'c and Szab\'o states that for any connected H, the lower threshold and the upper threshold of the Avoider-Enforcer H-game played on Kn are not of the same order in n. Until now, the conjecture has been verified only for stars, by Grzesik, Mikala\v{c}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
Permanent Link: http://hdl.handle.net/11104/0287751