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 Kn 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(K3; 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(K3; 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