A threshold for the Maker-Breaker clique game

DOI10.1002/rsa.20489zbMath1302.05120OpenAlexW2069210236MaRDI QIDQ2925528

Miloš Stojaković, Tobias Müller

Publication date: 16 October 2014

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

Full work available at URL: https://doi.org/10.1002/rsa.20489

zbMATH Keywords

random graphspositional gamesclique game

Mathematics Subject Classification ID

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

Related Items

A remark on the tournament game ⋮ \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs ⋮ Client-waiter games on complete and random graphs ⋮ Waiter-client triangle-factor game on the edges of the complete graph ⋮ On the threshold for the Maker-BreakerH-game ⋮ Maker‐breaker games on random geometric graphs ⋮ Maker-Breaker Games on Randomly Perturbed Graphs

Cites Work

• Threshold functions
• Positional games and the second moment method
• Hitting time results for Maker-Breaker games
• Clique percolation
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Regularity and Positional Games
• Biased Positional Games
• Sharp thresholds of graph properties, and the $k$-sat problem
• Positional games on random graphs
• Combinatorial Games
• A Solution of the Shannon Switching Game
• Biased positional games for which random strategies are nearly optimal