### Abstract

Let P be a monotone increasing 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 satisfies the property P. It is clear that in order for Maker to have a chance of winning, G itself must satisfy P. We prove that if G satisfies P in some strong sense, that is, if one has to delete sufficiently many edges from G in order to obtain a graph that does not satisfy P, then Maker has a winning strategy for this game. We also consider a different notion of satisfying some property in a strong sense, which is motivated by a problem of Duffus, Łuczak and Rödl [6].

Original language | English (US) |
---|---|

Pages (from-to) | 481-491 |

Number of pages | 11 |

Journal | Combinatorics Probability and Computing |

Volume | 19 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2010 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

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

## Cite this

*Combinatorics Probability and Computing*,

*19*(4), 481-491. https://doi.org/10.1017/S0963548310000064