The Containment Game in the plane: between the Firefighter Problem and Conway's Angel Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908735533744128 |
|---|---|
| author | Feldheim, Ohad Noy Israeli, Itamar |
| author_facet | Feldheim, Ohad Noy Israeli, Itamar |
| contents | The containment game is a full information game for two players, initialised with a set of occupied vertices in an infinite connected graph $G$. On the $t$-th turn, the first player, called Spreader, extends the occupied set to $g(t)$ adjacent vertices, and then the second player, called Container, removes $q$ unoccupied vertices from the graph. If the spreading process continues perpetually -- Spreader wins, and otherwise -- Container wins. For $g=\infty$ this game reduces to a solitaire game for Container, known as the Firefighter Problem. On $\mathbb{Z}^2$, for $q=1/k$ and $g\equiv 1$ it is equivalent to Conway's Angel Problem.
We introduce the game, and writing $q(G,g)$ for the set of $q$ values for which Container wins against a given $g(t)$, we study the minimal asymptotics of $g(t)$ such that $q(G,g)=q(G,\infty)$, i.e. for which defeating Spreader is as hard as winning the Firefighter Problem solitaire. We show, by providing explicit winning strategies, a sub-linear upper bound $g(t)=O(t^{6/7})$ and a lower bound of $g(t)=Ω(t^{1/2})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_10081 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Containment Game in the plane: between the Firefighter Problem and Conway's Angel Problem Feldheim, Ohad Noy Israeli, Itamar Combinatorics 05C57, 91A46, 91A43 G.2.2 The containment game is a full information game for two players, initialised with a set of occupied vertices in an infinite connected graph $G$. On the $t$-th turn, the first player, called Spreader, extends the occupied set to $g(t)$ adjacent vertices, and then the second player, called Container, removes $q$ unoccupied vertices from the graph. If the spreading process continues perpetually -- Spreader wins, and otherwise -- Container wins. For $g=\infty$ this game reduces to a solitaire game for Container, known as the Firefighter Problem. On $\mathbb{Z}^2$, for $q=1/k$ and $g\equiv 1$ it is equivalent to Conway's Angel Problem. We introduce the game, and writing $q(G,g)$ for the set of $q$ values for which Container wins against a given $g(t)$, we study the minimal asymptotics of $g(t)$ such that $q(G,g)=q(G,\infty)$, i.e. for which defeating Spreader is as hard as winning the Firefighter Problem solitaire. We show, by providing explicit winning strategies, a sub-linear upper bound $g(t)=O(t^{6/7})$ and a lower bound of $g(t)=Ω(t^{1/2})$. |
| title | The Containment Game in the plane: between the Firefighter Problem and Conway's Angel Problem |
| topic | Combinatorics 05C57, 91A46, 91A43 G.2.2 |
| url | https://arxiv.org/abs/2307.10081 |