Hitting time results for Maker-Breaker games

الأصل · EN

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