2019/01/02 by Kronenberg, Gal, Mond, Adva, Naor, Alon · 1 citation
#05C57 #05C80 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1901.00351
We introduce a new type of positional games, played on a vertex set of a graph. Given a graph G, two players claim vertices of G, where the outcome of the game is determined by the subgraphs of G induced by the vertices claimed by each player (or by one of them). We study classical positional games such as Maker-Breaker, Avoider-Enforcer, Waiter-Client and Client-Waiter games, where the board of the game is the vertex set of the binomial random graph G∼ G(n,p). Under these settings, we consider those games where the target sets are the vertex sets of all graphs containing a copy of a fixed graph H, called H-games, and focus on those cases where H is a clique or a cycle. We show that, similarly to the edge version of H-games, there is a strong connection between the threshold probability for these games and the one for the corresponding vertex Ramsey property (that is, the property that every r-vertex-coloring of G(n,p) spans a monochromatic copy of H). Another similarity to the edge version of these games we demonstrate, is that the games in which H is a triangle or a forest present a different behavior compared to the general case.