The diameter game

DOI10.1002/RSA.20280MaRDI QIDQ3055780zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(12)

• The random graph intuition for the tournament game
• 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?

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)