On Avoider-Enforcer games

József Balogh, Ryan Martin

Research output: Contribution to journalArticlepeer-review


In the Avoider-Enforcer game on the complete graph Kn, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property P, Enforcer wins the game if Avoider's graph has the property P. An important parameter is τE(P), the smallest integer t such that Enforcer can win the game against any opponent in t rounds. In this paper, let ℱ be an arbitrary family of graphs and P be the property that a member of ℱ is a subgraph or is an induced subgraph. We determine the asymptotic value of τE(P) when ℱ contains no bipartite graph and establish that τE(P) = o(n2)if ℱ contains a bipartite graph. The proof uses the game of JumbleG and the Szemeredi regularity lemma.

Original languageEnglish (US)
Pages (from-to)901-908
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2009


  • Avoider-Enforcer
  • JumbleG
  • Positional games
  • Regularity lemma

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'On Avoider-Enforcer games'. Together they form a unique fingerprint.

Cite this