The diameter game

DOI10.1002/RSA.20280zbMATH Open1198.91049arXiv1605.05698OpenAlexW2953178286MaRDI QIDQ3055780FDOQ3055780

Authors: József Balogh, Ryan R. Martin, András Pluhár 

Publication date: 9 November 2010

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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)n^{1/8}/(lnn{)}^{3/8}$. In addition, we investigate $d$-diameter games for $dge3$. 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.

Full work available at URL: https://arxiv.org/abs/1605.05698

Recommendations

• Biased Positional Games
• The picker-chooser diameter game
• scientific article; zbMATH DE number 3877237
• Biased positional games for which random strategies are nearly optimal
• Biased positional games and the phase transition

zbMATH Keywords

diameterrandom graphspositional games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Planarity, Colorability, and Minor Games
• Remarks on positional games. I
• Regularity and Positional Games
• Biased Positional Games
• A Solution of the Shannon Switching Game
• Biased positional games for which random strategies are nearly optimal
• On the complexity of some two-person perfect-information games
• Deterministic Graph Games and a Probabilistic Intuition
• Biased positional games and the phase transition
• Positional Games
• The accelerated \(k\)-in-a-row game
• Title not available (Why is that?)
• On a theorem of Beck
• Title not available (Why is that?)

Cited In (12)

• The positive minimum degree game on sparse graphs
• The picker-chooser diameter game
• On chooser-picker positional games
• The Hats game. On maximum degree and diameter
• Winning fast in fair biased maker-breaker games
• Connector-breaker games on random boards
• Walker-breaker games on \(G_{n, p}\)
• Biased orientation games
• On the clique-game
• Spanning Structures in Walker–Breaker Games
• How fast can maker win in fair biased games?
• The random graph intuition for the tournament game

This page was built for publication: The diameter game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055780)