Positional games on random graphs

DOI10.1002/RSA.20059MaRDI QIDQ4667863zbMATH OpenOpenAlexFDO

Authors Miloš Stojaković, Tibor Szabó

Publication date 21 April 2005

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

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

Mathematics Subject Classification ID

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

Abstract: We introduce and study Maker/Breaker-type positional games on random graphs. Our main concern is to determine the threshold probability $p_F$ for the existence of Maker's strategy to claim a member of $F$ in the unbiased game played on the edges of random graph $G(n,p)$, for various target families $F$ of winning sets. More generally, for each probability above this threshold we study the smallest bias $b$ such that Maker wins the $(1:b)$ biased game. We investigate these functions for a number of basic games, like the connectivity game, the perfect matching game, the clique game and the Hamiltonian cycle game.

Recommendations

• Biased positional games for which random strategies are nearly optimal
• Sharp thresholds for half-random games. II
• Sharp thresholds for half-random games. I.
• Random-player maker-breaker games
• Biased games on random boards

Cites work

• A note on Hamiltonian circuits
• A Solution of the Shannon Switching Game
• Biased positional games and the phase transition
• Biased positional games for which random strategies are nearly optimal
• Hitting time for \(k\) edge-disjoint spanning trees in a random graph
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 3388040 (Why is no real title available?)
• Positional games and the second moment method
• Remarks on positional games. I

Cited in

(52)

• Equilibria in nonantagonistic positional games on graphs and searching for them
• Positional games and the second moment method
• Maker-breaker percolation games. II: Escaping to infinity
• Sharp thresholds for half-random games. II
• Connector-breaker games on random boards
• Localization game for random geometric graphs
• Combinatorial game distributions of Steiner systems
• On the WalkerMaker-WalkerBreaker games
• Fast strategies in Waiter-Client games
• Upper bounds on positional Paris-Harrington games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Online balanced graph avoidance games
• The threshold bias of the clique-factor game
• Random directed graphs are robustly Hamiltonian
• On the threshold for the maker-breaker H-game
• Creating cycles in walker-breaker games
• Hitting time results for maker-breaker games
• A threshold for the maker-breaker clique game
• Sharp thresholds for half-random games. I.
• Fast strategies in maker-breaker games played on random boards
• Hitting Time Theorems for Random Matrices
• Generating random graphs in biased maker-breaker games
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• scientific article; zbMATH DE number 3945911 (Why is no real title available?)
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• On Biased Positional Games
• scientific article; zbMATH DE number 1047712 (Why is no real title available?)
• scientific article; zbMATH DE number 7021370 (Why is no real title available?)
• The Maker-Breaker Rado game on a random set of integers
• Maker–Breaker percolation games I: crossing grids
• Maker-Breaker games on randomly perturbed graphs
• Strong games played on random graphs
• Maker-breaker games on random geometric graphs
• Biased games on random boards
• Efficient winning strategies in random-turn maker-breaker games
• The random graph intuition for the tournament game
• Component games on regular graphs
• A threshold for the maker-breaker clique game
• Probabilistic intuition holds for a class of small subgraph games
• Biased positional games for which random strategies are nearly optimal
• Maker-Breaker total domination game on cubic graphs
• Galton–Watson games
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Multistage positional games
• On the clique-game
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Complexity of maker-breaker games on edge sets of graphs
• The Maker-Breaker percolation game on the square lattice
• Component games on random graphs
• The Maker-Breaker percolation game on a random board
• A remark on the tournament game
• Random-player maker-breaker games

This page was built for publication: Positional games on random graphs

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