On the threshold for the Maker-Breaker H-game

Original · EN

We study the Maker-Breaker H-game played on the edge set of the random graph Gₙ,ₚ. In this game two players, Maker and Breaker, alternately claim unclaimed edges of Gₙ,ₚ, until all the edges are claimed. Maker wins if he claims all the 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ₙ,ₚ with respect to the graph H.