Generating random graphs in biased Maker-Breaker games

DOI10.1002/rsa.20619zbMath1330.05143arXiv1310.4096OpenAlexW1910826241WikidataQ105583304 ScholiaQ105583304MaRDI QIDQ3460510

Asaf Ferber, Michael Krivelevich, Humberto Naves

Publication date: 7 January 2016

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

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

zbMATH Keywords

random graphsgames

Mathematics Subject Classification ID

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

Related Items (9)

Creating cycles in walker-breaker games ⋮ Spanning Structures in Walker–Breaker Games ⋮ The threshold bias of the clique-factor game ⋮ Finding Hamilton cycles in random graphs with few queries ⋮ Multistage positional games ⋮ Fast strategies in Waiter-Client games ⋮ Manipulative Waiters with Probabilistic Intuition ⋮ Connector-breaker games on random boards ⋮ Maker-Breaker Games on Randomly Perturbed Graphs

Cites Work

• Fast embedding of spanning trees in biased maker-breaker games
• On two Hamilton cycle problems in random graphs
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• Almost spanning subgraphs of random graphs after adversarial edge removal
• Building Spanning Trees Quickly in Maker-Breaker Games
• Asymptotic random graph intuition for the biased connectivity game
• Local resilience of almost spanning trees in random graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Dirac's theorem for random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Local resilience of graphs
• Biased Positional Games
• A Solution of the Shannon Switching Game
• Biased positional games for which random strategies are nearly optimal

This page was built for publication: Generating random graphs in biased Maker-Breaker games