Hitting time results for Maker-Breaker games

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ć and Szabó.

24 pages

References in corpus (2)

• Local resilience and Hamiltonicity Maker-Breaker games in random-regular graphs
• On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs

Cited by in corpus (10)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamilton Cycles in Random Graphs: a bibliography
• Creating cycles in Walker-Breaker games
• Hitting time theorems for random matrices
• Waiter-Client and Client-Waiter Hamiltonicity games on random graphs
• Biased Games On Random Boards
• On the trace of random walks on random graphs
• Positional games on randomly perturbed graphs
• Fast strategies in Maker-Breaker games played on random boards
• On the number of Hamilton cycles in sparse random graphs