On the threshold for the Maker‐Breaker H‐game1. Issue 3 (24th December 2015)

• Record Type: Journal Article
• Authors: Nenadov, Rajko; Steger, Angelika; Stojaković, Miloš
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 558
• Page End: 578
• Publication Date: 2015-12-24
• Subjects: positional games -- random graphs -- Maker‐Breaker; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20628
• Languages: English
• ISSNs: 1042-9832

Abstract

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