Hitting time results for Maker-Breaker games Extended Abstract
Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, Michael Krivelevich · 2011
We analyze classical Maker-Breaker games played on the edge set of a randomly generated graph G.We consider the random graph process and analyze, for each of the properties "being spanning k-vertex-connected" , "admitting a perfect matching", and "being Hamiltonian", the first time when Maker starts having a winning strategy for building a graph possessing the target property (the so called hitting time).We prove that typically it happens precisely at the time the random graph process first reaches minimum degree 2k, 2 and 4, respectively, which is clearly optimal.The latter two statements settle conjectures of Stojaković and Szabó.We also consider a general-purpose game, the expander game, which is a main ingredient of our proofs and might be of an independent interest.