The Maker-Breaker percolation game on a random board
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909121628864512 |
|---|---|
| author | Dvořák, Vojtěch Mond, Adva Souza, Victor |
| author_facet | Dvořák, Vojtěch Mond, Adva Souza, Victor |
| contents | The $(m,b)$ Maker-Breaker percolation game on $(\mathbb{Z}^2)_p$, introduced by Day and Falgas-Ravry, is played in the following way. Before the game starts, each edge of $\mathbb{Z}^2$ is removed independently with probability $1-p$. After that, Maker chooses a vertex $v_0$ to protect. Then, in each round Maker and Breaker claim respectively $m$ and $b$ unclaimed edges of $G$. Breaker wins if after the removal of the edges claimed by him the component of $v_0$ becomes finite, and Maker wins if she can indefinitely prevent Breaker from winning.
We show that for any $p < 1$, Breaker almost surely has a wining strategy for the $(1,1)$ game on $(\mathbb{Z}^2)_p$. This fully answers a question of Day and Falgas-Ravry, who showed that for $p = 1$ Maker has a winning strategy for the $(1,1)$ game. Further, we show that in the $(2,1)$ game on $(\mathbb{Z}^2)_p$ Maker almost surely has a winning strategy whenever $p > 0.9402$, while Breaker almost surely has a winning strategy whenever $p < 0.5278$. This shows that the threshold value of $p$ above which Maker has a winning strategy for the $(2,1)$ game on $\mathbb{Z}^2$ is non-trivial. In fact, we prove similar results in various settings, including other lattices and biases $(m,b)$.
These results extend also to the most general case, which we introduce, where each edge is given to Maker with probability $α$ and to Breaker with probability $β$ before the game starts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17547 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Maker-Breaker percolation game on a random board Dvořák, Vojtěch Mond, Adva Souza, Victor Probability Combinatorics The $(m,b)$ Maker-Breaker percolation game on $(\mathbb{Z}^2)_p$, introduced by Day and Falgas-Ravry, is played in the following way. Before the game starts, each edge of $\mathbb{Z}^2$ is removed independently with probability $1-p$. After that, Maker chooses a vertex $v_0$ to protect. Then, in each round Maker and Breaker claim respectively $m$ and $b$ unclaimed edges of $G$. Breaker wins if after the removal of the edges claimed by him the component of $v_0$ becomes finite, and Maker wins if she can indefinitely prevent Breaker from winning. We show that for any $p < 1$, Breaker almost surely has a wining strategy for the $(1,1)$ game on $(\mathbb{Z}^2)_p$. This fully answers a question of Day and Falgas-Ravry, who showed that for $p = 1$ Maker has a winning strategy for the $(1,1)$ game. Further, we show that in the $(2,1)$ game on $(\mathbb{Z}^2)_p$ Maker almost surely has a winning strategy whenever $p > 0.9402$, while Breaker almost surely has a winning strategy whenever $p < 0.5278$. This shows that the threshold value of $p$ above which Maker has a winning strategy for the $(2,1)$ game on $\mathbb{Z}^2$ is non-trivial. In fact, we prove similar results in various settings, including other lattices and biases $(m,b)$. These results extend also to the most general case, which we introduce, where each edge is given to Maker with probability $α$ and to Breaker with probability $β$ before the game starts. |
| title | The Maker-Breaker percolation game on a random board |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2402.17547 |