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 , mathematics , enhanced data rates for gsm evolution , 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom