Maker-breaker games on random geometric graphs

DOI10.1002/RSA.20572MaRDI QIDQ5256385zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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

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)

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$.

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

Cites work

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

Cited in

(8)

• scientific article; zbMATH DE number 7069683 (Why is no real title available?)
• 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

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)