We consider the Maker–Breaker positional game on the vertices of the n-dimensional hypercube {0,1}n with k-dimensional subcubes as winning sets. We describe a pairing strategy which allows Breaker to ...win if n is a power of 4 and k≥n/4+1. Our results also imply that for all n≥3 there is a Breaker's win pairing strategy if k≥⌊37n⌋+1.
On strong avoiding games Stojaković, Miloš; Stratijev, Jelena
Discrete mathematics,
March 2023, 2023-03-00, Letnik:
346, Številka:
3
Journal Article
Recenzirano
Given an increasing graph property F, the strong Avoider-Avoider F game is played on the edge set of a complete graph. Two players, Red and Blue, take turns in claiming previously unclaimed edges ...with Red going first, and the player whose graph possesses F first loses the game. If the property F is “containing a fixed graph H”, we refer to the game as the H game.
We prove that Blue has a winning strategy in two strong Avoider-Avoider games, P4 game and CC>3 game, where CC>3 is the property of having at least one connected component on more than three vertices.
We also study a variant, the strong CAvoider-CAvoider games, with additional requirement that the graph of each of the players must stay connected throughout the game. We prove that Blue has a winning strategy in the strong CAvoider-CAvoider games S3 and P4, as well as in the Cycle game, where the players aim at avoiding all cycles.
We introduce the Maker–Breaker domination game, a two player game on a graph. At his turn, the first player, Dominator, selects a vertex in order to dominate the graph while the other player, ...Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn. This game is a particular instance of the so-called Maker–Breaker games, that is studied here in a combinatorial context. In this paper, we first prove that deciding the winner of the Maker–Breaker domination game is pspace-complete, even for bipartite graphs and split graphs. It is then showed that the problem is polynomial for cographs and trees. In particular, we define a strategy for Dominator that is derived from a variation of the dominating set problem, called the pairing dominating set problem.
We study the Maker–Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a dominating set of the ...graph wins. As the Maker–Breaker version, this game is PSPACE-complete on split and bipartite graphs. Our main result is a linear time algorithm to solve this game in forests. We also give a characterization of the cycles where the first player has a winning strategy.
Let Λ be an infinite connected graph, and let v0 be a vertex of Λ. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of Λ are ...marked as unsafe. On each of her turns, Maker marks p unsafe edges as safe, while on each of his turns Breaker takes q unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing v0 becomes finite. Otherwise if Maker is able to ensure that v0 remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given (p,q) and (Λ,v0), we would like to know: which of the two players has a winning strategy?
Our main result in this paper establishes that when Λ=Z2 and v0 is any vertex, Maker has a winning strategy whenever p≥2q, while Breaker has a winning strategy whenever 2p≤q. In addition, we completely determine which of the two players has a winning strategy for every pair (p,q) when Λ is an infinite d-regular tree. Finally, we give some results for general graphs and lattices and pose some open problems.
Let r≥4 be an integer and consider the following game on the complete graph Kn for n∈rZ: Two players, Maker and Breaker, alternately claim previously unclaimed edges of Kn such that in each turn ...Maker claims one and Breaker claims b∈N edges. Maker wins if her graph contains a Kr-factor, that is a collection of n/r vertex-disjoint copies of Kr, and Breaker wins otherwise. In other words, we consider a b-biased Kr-factor Maker–Breaker game. We show that the threshold bias for this game is of order n2/(r+2). This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al. who resolved the case r∈{3,4} up to a logarithmic factor.
We give upper bounds for a positional game – in the sense of Beck – based on the Paris–Harrington Theorem for bi-colorings of graphs and uniform hypergraphs of arbitrary dimension. The bounds for the ...positional game show a striking difference when compared to the bounds for the combinatorial principle itself. Our results confirm a phenomenon already observed by Beck and others: the upper bounds for the game version of a combinatorial principle are drastically smaller than the upper bounds for the principle itself. In the case of Paris–Harrington games the difference is qualitatively very striking. For example, the bounds for the game on 3-uniform hypergraphs are a fixed stack of exponentials while the bounds for the corresponding combinatorial principle are known to be at least Ackermannian. For higher dimensions, the combinatorial Paris–Harrington numbers are known to be cofinal in the Schwichtenberg–Wainer Hierarchy of fast-growing functions up to the ordinal ε0, while we show that the game Paris–Harrington numbers are bounded by fixed stacks of exponentials.
Waiter–Client and Client–Waiter games are two–player, perfect information games, with no chance moves, played on a finite set (board) with special subsets known as the winning sets. Each round of the ...biased $(1:q)$ Waiter–Client game begins with Waiter offering $q+1$ previously unclaimed elements of the board to Client, who claims one and leaves the remaining $q$ elements to be claimed by Waiter immediately afterwards. In a $(1:q)$ Client–Waiter game, play occurs in the same way except in each round, Waiter offers $t$ elements for any $t$ in the range $1\leqslant t\leqslant q+1$. If Client fully claims a winning set by the time all board elements have been offered, he wins in the Client–Waiter game and loses in the Waiter–Client game. We give an estimate for the threshold bias (i.e. the unique value of $q$ at which the winner of a $(1:q)$ game changes) of the $(1:q)$ Waiter–Client and Client–Waiter versions of two different games: the non–2–colourability game, played on the edge set of a complete $k$–uniform hypergraph, and the $k$–SAT game. More precisely, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the non–2–colourability game is $\frac{1}{n}\binom{n}{k}2^{\mathcal{O}_k(k)}$ and $\frac{1}{n}\binom{n}{k}2^{-k(1+o_k(1))}$ respectively. Additionally, we show that the threshold bias for the Waiter–Client and Client–Waiter versions of the $k$–SAT game is $\frac{1}{n}\binom{n}{k}$ up to a factor that is exponential and polynomial in $k$ respectively. This shows that these games exhibit the probabilistic intuition.
PDF
