On the Chvátal-Erdős triangle game

József Balogh, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume18
Issue number1
DOIs
StatePublished - 2011

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'On the Chvátal-Erdős triangle game'. Together they form a unique fingerprint.

Cite this