The diameter game

József Balogh, Ryan Martin, András Pluhár

Research output: Contribution to journalArticlepeer-review

Abstract

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given - usually monotone - property. Here we introduce the d-diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2-diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n1/8/(ln n)3/8. In addition, we investigate d-diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case.

Original languageEnglish (US)
Pages (from-to)369-389
Number of pages21
JournalRandom Structures and Algorithms
Volume35
Issue number3
DOIs
StatePublished - Oct 2009

Keywords

  • Diameter
  • Positional games
  • Random graphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The diameter game'. Together they form a unique fingerprint.

Cite this