Maker-breaker games on random geometric graphs

DOI10.1002/RSA.20572zbMATH Open1320.05083DBLPjournals/rsa/BeveridgeDFMS14arXiv1309.5759OpenAlexW2144829613WikidataQ57401420 ScholiaQ57401420MaRDI QIDQ5256385FDOQ5256385

Authors: Andrew Beveridge, Andrzej Dudek, Tobias Müller, Miloš Stojaković, Alan Frieze 

Publication date: 22 June 2015

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

Abstract: In a Maker-Breaker game on a graph $G$, Breaker and Maker alternately claim edges of $G$. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played on random geometric graphs. For each of our four games we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $noinfty$, the graph becomes Maker-win the very moment it satisfies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree is at least two; Maker wins the Hamilton cycle game as soon as the minimum degree is at least four; Maker wins the perfect matching game as soon as the minimum degree is at least two and every edge has at least three neighbouring vertices; and Maker wins the $H$-game as soon as there is a subgraph from a finite list of "minimal graphs". These results also allow us to give precise expressions for the limiting probability that $G(n,r)$ is Maker-win in each case, where $G(n,r)$ is the graph on $n$ points chosen uniformly at random on the unit square with an edge between two points if and only if their distance is at most $r$.

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

Recommendations

• Hitting time results for maker-breaker games
• Maker-Breaker games on randomly perturbed graphs
• Positional games on random graphs
• Hitting time results for maker-breaker games (extended abstract)
• Fast strategies in maker-breaker games played on random boards

zbMATH Keywords

random geometric graphsmaker-breaker games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Random Geometric Graphs
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Two-point concentration in random geometric graphs
• Random Plane Networks
• Positional games and the second moment method
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Regularity and Positional Games
• Biased Positional Games
• A Solution of the Shannon Switching Game
• On the threshold for the maker-breaker \(H\)-game
• Hitting time results for maker-breaker games
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Title not available (Why is that?)
• Positional games on random graphs
• The longest edge of the random minimal spanning tree
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• The cover time of random geometric graphs
• A threshold for the maker-breaker clique game
• On the chromatic number of random geometric graphs
• Random channel assignment in the plane

Cited In (8)

• Maker-breaker percolation games. II: Escaping to infinity
• Hitting time results for maker-breaker games (extended abstract)
• The acquaintance time of (percolated) random geometric graphs
• Maker–Breaker percolation games I: crossing grids
• Exponential rate for the contact process extinction time
• Galton–Watson games
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Title not available (Why is that?)

This page was built for publication: Maker-breaker games on random geometric graphs

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