Mathematics – Combinatorics
Scientific paper
2010-08-11
Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA'11), 900--912, 2011
Mathematics
Combinatorics
24 pages
Scientific paper
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}.
Ben-Shimon Sonny
Ferber Asaf
Hefetz Dan
Krivelevich Michael
No associations
LandOfFree
Hitting time results for Maker-Breaker games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hitting time results for Maker-Breaker games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting time results for Maker-Breaker games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-479896