The Avoider-Enforcer game on hypergraphs of rank 3
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910896738009088 |
|---|---|
| author | Galliot, Florian Gledel, Valentin Parreau, Aline |
| author_facet | Galliot, Florian Gledel, Valentin Parreau, Aline |
| contents | In the Avoider-Enforcer convention of positional games, two players, Avoider and Enforcer, take turns selecting vertices from a hypergraph H. Enforcer wins if, by the time all vertices of H have been selected, Avoider has completely filled an edge of H with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21672 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Avoider-Enforcer game on hypergraphs of rank 3 Galliot, Florian Gledel, Valentin Parreau, Aline Combinatorics Discrete Mathematics In the Avoider-Enforcer convention of positional games, two players, Avoider and Enforcer, take turns selecting vertices from a hypergraph H. Enforcer wins if, by the time all vertices of H have been selected, Avoider has completely filled an edge of H with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms. |
| title | The Avoider-Enforcer game on hypergraphs of rank 3 |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.21672 |