Generalized saturation game
| Autor: | Patkós, Balázs, Stojaković, Miloš, Stratijev, Jelena, Vizer, Máté |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We study the following game version of the generalized graph Tur\'an 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. Comment: 26 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|