Hitting time results for maker-breaker games

DOI10.1002/RSA.20392zbMATH Open1247.91036arXiv1008.1865OpenAlexW2145342041MaRDI QIDQ2909241FDOQ2909241

Authors: Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, Michael Krivelevich 

Publication date: 30 August 2012

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

Abstract: We study Maker-Breaker games played on the edge set of a random graph. Specifically, we consider the random graph process and analyze the first time in a typical random graph process that Maker starts having a winning strategy for his final graph to admit some property $mP$. We focus on three natural properties for Maker's graph, namely being $k$-vertex-connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the $k$-vertex connectivity game exactly at the time the random graph process first reaches minimum degree $2k$; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree $2$; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree $4$. The latter two statements settle conjectures of Stojakovi'{c} and Szab'{o}.

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

Recommendations

• Hitting time results for maker-breaker games (extended abstract)
• Fast winning strategies in maker-breaker games
• On the threshold for the maker-breaker \(H\)-game
• Efficient winning strategies in random-turn maker-breaker games
• Winning fast in biased maker-breaker games
• Random-player maker-breaker games
• Maker-breaker resolving game
• Fast strategies in maker-breaker games played on random boards
• On the WalkerMaker-WalkerBreaker games
• The measurability of hitting times

zbMATH Keywords

hitting timerandom graphsmaker-breaker games

Mathematics Subject Classification ID

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

Cites Work

• Biased Positional Games
• Combinatorial Games
• A Solution of the Shannon Switching Game
• On a combinatorial game
• On two problems regarding the Hamiltonian cycle game
• Fast winning strategies in maker-breaker games
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Positional games on random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On two Hamilton cycle problems in random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Global maker-breaker games on sparse graphs
• On positional games
• A Winning Strategy for the Ramsey Graph Game
• Hitting time for \(k\) edge-disjoint spanning trees in a random graph
• Winning Fast in Sparse Graph Construction Games

Cited In (16)

• Maker-Breaker games on randomly perturbed graphs
• Random directed graphs are robustly Hamiltonian
• Hitting time results for maker-breaker games (extended abstract)
• Creating cycles in walker-breaker games
• Biased games on random boards
• Hitting Time Theorems for Random Matrices
• A threshold for the maker-breaker clique game
• Waiter-client triangle-factor game on the edges of the complete graph
• Random-player maker-breaker games
• Fast strategies in maker-breaker games played on random boards
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Efficient winning strategies in random-turn maker-breaker games
• Strong games played on random graphs
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• On the Hamiltonicity of the \(k\)-regular graph game
• Maker-breaker games on random geometric graphs

This page was built for publication: Hitting time results for maker-breaker games

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