Počet záznamů: 1  

On the Separation Conjecture in Avoider-Enforcer Games

  1. 1.
    0494643 - ÚI 2020 US eng J - Článek v odborném periodiku
    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
    Grant CEP: GA ČR GJ16-07822Y
    Institucionální podpora: RVO:67985807
    Obor OECD: Pure mathematics
    Impakt faktor: 1.306, rok: 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
    Trvalý link: http://hdl.handle.net/11104/0287751

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    0494643pre2.pdf4431.5 KBarXiv.orgAutorský preprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.