Hitting time results for maker-breaker games

DOI10.1002/RSA.20392MaRDI QIDQ2909241zbMATH OpenOpenAlexFDO

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)

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

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)

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}.

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

Cites work

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

Cited in

(16)

• Maker-breaker games on random geometric graphs
• 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

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)