On Avoider-Enforcer games
| Autor: | József Balogh, Ryan Martin |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Computer Science::Computer Science and Game Theory Mathematics::Combinatorics General Mathematics 010102 general mathematics Complete graph Induced subgraph Szemerédi regularity lemma 0102 computer and information sciences 16. Peace & justice 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics 91A46 05C35 05C15 Bipartite graph FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Graph property Mathematics |
| DOI: | 10.48550/arxiv.1605.05706 |
| Popis: | In the Avoider-Enforcer game on the complete graph $K_n$, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property $\mathcal{P}$, Enforcer wins the game if Avoider's graph has the property $\mathcal{P}$. An important parameter is $\tau_E({\cal P})$, the smallest integer $t$ such that Enforcer can win the game against any opponent in $t$ rounds. In this paper, let $\mathcal{F}$ be an arbitrary family of graphs and $\mathcal{P}$ be the property that a member of $\mathcal{F}$ is a subgraph or is an induced subgraph. We determine the asymptotic value of $\tau_E(\mathcal{P})$ when $\mathcal{F}$ contains no bipartite graph and establish that $\tau_E(\mathcal{P})=o(n^2)$ if $\mathcal{F}$ contains a bipartite graph. The proof uses the game of JumbleG and the Szemer\'edi Regularity Lemma. Comment: 10 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|