Premium
Positional games on random graphs
Author(s) -
Stojaković Miloš,
Szabó Tibor
Publication year - 2005
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.20059
Subject(s) - combinatorics , random graph , combinatorial game theory , random regular graph , hamiltonian path , mathematics , graph , strategy , repeated game , mathematical economics , discrete mathematics , game theory , computer science , chordal graph , 1 planar graph
We introduce and study Maker/Breaker‐type positional games on random graphs. Our main concern is to determine the threshold probability p ℱ for the existence of Maker's strategy to claim a member of ℱ in the unbiased game played on the edges of random graph G ( n, p ), for various target families ℱ of winning sets. More generally, for each probability above this threshold we study the smallest bias b such that Maker wins the (1 : b ) biased game. We investigate these functions for a number of basic games, like the connectivity game, the perfect matching game, the clique game and the Hamiltonian cycle game. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005