On the Constructor–Blocker game

József Balogh, Ce Chen, Sean English

Research output: Contribution to journalArticlepeer-review

Abstract

In the Constructor–Blocker game, two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph (Formula presented.). For given graphs (Formula presented.) and (Formula presented.), Constructor can only claim edges that leave her graph (Formula presented.) -free, while Blocker has no restrictions. Constructor's goal is to build as many copies of (Formula presented.) as she can, while Blocker attempts to minimize the number of copies of (Formula presented.) in Constructor's graph. The game ends once there are no more edges that Constructor can claim. The score (Formula presented.) of the game is the number of copies of (Formula presented.) in Constructor's graph at the end of the game when both players play optimally and Constructor plays first. In this paper, we extend results of Patkós, Stojaković and Vizer on (Formula presented.) to many pairs of (Formula presented.) and (Formula presented.) : We determine (Formula presented.) when (Formula presented.) and (Formula presented.), also when both (Formula presented.) and (Formula presented.) are odd cycles, using Szemerédi's Regularity Lemma. We also obtain bounds of (Formula presented.) when (Formula presented.) and (Formula presented.).

Original languageEnglish (US)
Pages (from-to)492-507
Number of pages16
JournalJournal of Graph Theory
Volume108
Issue number3
DOIs
StateAccepted/In press - 2024

Keywords

  • generalized Turán number
  • jumbleG
  • positional games
  • Regularity Lemma

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On the Constructor–Blocker game'. Together they form a unique fingerprint.

Cite this