Generating random graphs in biased maker-breaker games

DOI10.1002/RSA.20619MaRDI QIDQ3460510zbMATH OpenOpenAlexWikidataFDO

Authors 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

gamesrandom graphs

Mathematics Subject Classification ID

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

Abstract: We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker-Breaker games. In particular, we show that for $b=oleft(sqrtnight)$, Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a $(1:b)$ game on $E(K_n)$. As another application, we show that for $b=Thetaleft(n/lnnight)$, playing a $(1:b)$ game on $E(K_n)$, Maker can build a graph which contains copies of all spanning trees having maximum degree $Delta=O(1)$ with a bare path of linear length (a bare path in a tree $T$ is a path with all interior vertices of degree exactly two in $T$).

Recommendations

• Asymptotic random graph intuition for the biased connectivity game
• Biased games on random boards
• Positional games on random graphs
• Random-player maker-breaker games
• Maker-Breaker games on randomly perturbed graphs

Cites work

• A Solution of the Shannon Switching Game
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Building spanning trees quickly in maker-breaker games
• Dirac's theorem for random graphs
• Fast embedding of spanning trees in biased maker-breaker games
• Fast winning strategies in maker-breaker games
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience of graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Weak and strong \(k\)-connectivity games

Cited in

(13)

• Connector-breaker games on random boards
• Fast strategies in Waiter-Client games
• The threshold bias of the clique-factor game
• Creating cycles in walker-breaker games
• Finding Hamilton cycles in random graphs with few queries
• Asymptotic random graph intuition for the biased connectivity game
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Maker-Breaker games on randomly perturbed graphs
• Spanning Structures in Walker–Breaker Games
• Manipulative waiters with probabilistic intuition
• Multistage positional games
• Doubly biased walker-breaker games
• Walker-breaker games on \(G_{n, p}\)

This page was built for publication: Generating random graphs in biased maker-breaker games

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