Premium
Asymptotic random graph intuition for the biased connectivity game
Author(s) -
Gebauer Heidi,
Szabó Tibor
Publication year - 2009
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.20279
Subject(s) - combinatorics , intuition , random graph , mathematics , graph , discrete mathematics , mathematical economics , psychology , cognitive science
We study biased Maker/Breaker games on the edges of the complete graph, as introduced by Chvátal and Erdős. We show that Maker, occupying one edge in each of his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 − o (1)) · $ {n \over \ln n} $ edges in each turn. This improves a result of Beck, and is asymptotically best possible as witnessed by the Breaker‐strategy of Chvátal and Erdős. We also give a strategy for Maker to occupy a graph with minimum degree c (where c = c ( n ) is a slowly growing function of n ) while playing against a Breaker who takes b ≤ (1 − o (1)) · $ {n \over \ln n} $ edges in each turn. This result improves earlier bounds by Krivelevich and Szabó. Both of our results support the surprising random graph intuition: the threshold bias is asymptotically the same for the game played by two “clever” players and the game played by two “random” players. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009