## Abstract

Given a graph G and positive integers n and q, let G(G; n, q) be the game played on the edges of the complete graph K_{n} in which the two players, Maker and Breaker, alternately claim 1 and q edges, respectively. Maker's goal is to occupy all edges in some copy of G; Breaker tries to prevent it. In their seminal paper on positional games, Chv́atal and Erdo{double acute}s proved that in the game G(K_{3}; n, q), Maker has a winning strategy if q ≥ 2√n, then Breaker has a winning strategy. In this note, we improve the latter of these bounds by describing a randomized strategy that allows Breaker to win the game G(K_{3}; n, q) whenever q ≥ (2 - 1/24)√n. Moreover, we provide additional evidence supporting the belief that this bound can be further improved to (√2 + o(1))√n.

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

Journal | Electronic Journal of Combinatorics |

Volume | 18 |

Issue number | 1 |

DOIs | |

State | Published - 2011 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics