Premium
On the threshold for the Maker‐Breaker H ‐game
Author(s) -
Nenadov Rajko,
Steger Angelika,
Stojaković Miloš
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20628
Subject(s) - circuit breaker , graph , combinatorics , enhanced data rates for gsm evolution , mathematics , discrete mathematics , mathematical economics , computer science , artificial intelligence , engineering , electrical engineering
We study the Maker‐Breaker H ‐game played on the edge set of the random graphG n , p. In this game two players, Maker and Breaker, alternately claim unclaimed edges ofG 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 ofG n , pwith respect to the graph H . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 558–578, 2016