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
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