Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2404.02288 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |