On the threshold for the Maker‐Breaker H‐game1. Issue 3 (24th December 2015) - Nenadov, Rajko; Steger, Angelika; Stojaković, Miloš
Abstract: We study the Maker‐Breaker H ‐game played on the edge set of the random graph G n, p . In this game two players, Maker and Breaker, alternately claim unclaimed edges of G n, p, until all edges are claimed. Maker wins if he claims all edges of a copy of a fixed graph H ; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an H ‐game is given by the threshold of the corresponding Ramsey property of G n, p with respect to the graph H . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 558–578, 2016