Generalized saturation game
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918037379088384 |
|---|---|
| author | Patkós, Balázs Stojaković, Miloš Stratijev, Jelena Vizer, Máté |
| author_facet | Patkós, Balázs Stojaković, Miloš Stratijev, Jelena Vizer, Máté |
| contents | We study the following game version of the generalized graph Turán problem. For two fixed graphs F and H, two players, Max and Mini, alternately claim unclaimed edges of the complete graph Kn such that the graph G of the claimed edges must remain F-free throughout the game. The game ends when no further edges can be claimed, i.e. when G becomes F-saturated. The H-score of the game is the number of copies of H in G. Max aims to maximize the H-score, while Mini wants to minimize it. The H-score of the game when both players play optimally is denoted by s1(n, #H, F) when Max starts, and by s2(n, #H, F) when Mini starts. We study these values for several natural choices of F and H. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02288 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized saturation game Patkós, Balázs Stojaković, Miloš Stratijev, Jelena Vizer, Máté Combinatorics Discrete Mathematics We study the following game version of the generalized graph Turán problem. For two fixed graphs F and H, two players, Max and Mini, alternately claim unclaimed edges of the complete graph Kn such that the graph G of the claimed edges must remain F-free throughout the game. The game ends when no further edges can be claimed, i.e. when G becomes F-saturated. The H-score of the game is the number of copies of H in G. Max aims to maximize the H-score, while Mini wants to minimize it. The H-score of the game when both players play optimally is denoted by s1(n, #H, F) when Max starts, and by s2(n, #H, F) when Mini starts. We study these values for several natural choices of F and H. |
| title | Generalized saturation game |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2404.02288 |