Playing to retain the advantage

Dan Hefetz, Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticle

Abstract

Let P be a monotone decreasing graph property, let G = (V, E) be a graph, and let q be a positive integer. In this paper, we study the (1 : q) Maker-Breaker game, played on the edges of G, in which Maker's goal is to build a graph that does not satisfy the property P. It is clear that in order for Maker to have a chance of winning, G must not satisfy P. We prove that if G is far from satisfying P, that is, if one has to delete sufficiently many edges from G in order to obtain a graph that satisfies P, then Maker has a winning strategy for this game. We also consider a different notion of being far from satisfying some property, which is motivated by a problem of Duffus, Łuczak and Rödl [D. Duffus, T. Łuczak and V. Rödl, Biased positional games on hypergraphs, Studia Scientarum Matematicarum Hung. 34 (1998), 141-149].

Original languageEnglish (US)
Pages (from-to)423-427
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Volume34
DOIs
StatePublished - Aug 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Positional games
  • monotone property

Fingerprint Dive into the research topics of 'Playing to retain the advantage'. Together they form a unique fingerprint.

  • Cite this